In-place interleaving of real/imaginary arrays

This seems like an obvious question but I've Googled around without
finding the answer.

Given an array containing n real values followed by n imaginaries, is
there a way of swapping them around in-place so as to end up with an
array of n complex numbers? Without allocating an extra buffer.

R0 R1 R2 R3 I0 I1 I2 I3
becomes
R0 I0 R1 I1 R2 I2 R3 I3

Clearly we can pick any starting location, identify the place where
the number we find there ought to go, take it there and repeat with
the number we find in this new location, until we find ourselves back
at the starting location we chose.

The entire interleave can be carried out by a number of loops like
this, but how to select a suitable set of starting points? (without
allocating an extra buffer to keep track of what we've done). We can
tell when we are finished by counting how many moves we've done in
total. The difficulty is when we are not finished, selecting a
starting point which has not been touched yet by a previous loop.

-- 
Andy Robinson, Seventh String Software, www.seventhstring.com

Replying to my own post, a slightly inelegant partial solution has
occurred to me, which would be perfectly practical where there are
only a small number of possible n's, none of them too huge. (e.g. n
is a power of 2 from 2^1 to 2^20, say, which would do for me).

Simply, write a test program to pre-compute suitable lists of
loop-start-points, and hardwire these 20 lists into the program!

But if anyone has a more general and/or more elegant solution, I'd
still like to know.

Thanks,
Andy Robinson, Seventh String Software, www.seventhstring.com

Andy Robinson wrote:
> This seems like an obvious question but I've Googled around without
> finding the answer.
> 
> Given an array containing n real values followed by n imaginaries, is
> there a way of swapping them around in-place so as to end up with an
> array of n complex numbers? Without allocating an extra buffer.
> 
> R0 R1 R2 R3 I0 I1 I2 I3
> becomes
> R0 I0 R1 I1 R2 I2 R3 I3
> 
> Clearly we can pick any starting location, identify the place where
> the number we find there ought to go, take it there and repeat with
> the number we find in this new location, until we find ourselves back
> at the starting location we chose.
> 
> The entire interleave can be carried out by a number of loops like
> this, but how to select a suitable set of starting points? (without
> allocating an extra buffer to keep track of what we've done). We can
> tell when we are finished by counting how many moves we've done in
> total. The difficulty is when we are not finished, selecting a
> starting point which has not been touched yet by a previous loop.
> 

Ask google about inplace matrix transpose. There are various
descriptions of how to do this. Depending upon the level of analysis
applied the methods for this vary from linear to N^4 where N=n*m of
an n x m matrix. The best methods are based on finite group theory
with the other end being a lot of small motions to reduce problem to
(n-1) x m and then repeating. The n x n case is trivial. Some
N log ( N ) codes are quite simple.

You didn't say what platform you're on so I'm not sure if this will help you 
out or not.  If this is a real-time system and you've got data coming in 
through two A/Ds then I'd suggest you look into getting the DMA to store 
them in interleaved fashion to begin with.  You tell the DMA the real part 
begins at "my_array" and the imaginary part at "my_array+1" and then set the 
increment mode to "index by 2" for both channels.

Brad

"Andy Robinson" <andy@seventhstring.com> wrote in message 
news:d196on$kl$1$8300dec7@news.demon.co.uk...
> This seems like an obvious question but I've Googled around without
> finding the answer.
>
> Given an array containing n real values followed by n imaginaries, is
> there a way of swapping them around in-place so as to end up with an
> array of n complex numbers? Without allocating an extra buffer.
>
> R0 R1 R2 R3 I0 I1 I2 I3
> becomes
> R0 I0 R1 I1 R2 I2 R3 I3
>
> Clearly we can pick any starting location, identify the place where
> the number we find there ought to go, take it there and repeat with
> the number we find in this new location, until we find ourselves back
> at the starting location we chose.
>
> The entire interleave can be carried out by a number of loops like
> this, but how to select a suitable set of starting points? (without
> allocating an extra buffer to keep track of what we've done). We can
> tell when we are finished by counting how many moves we've done in
> total. The difficulty is when we are not finished, selecting a
> starting point which has not been touched yet by a previous loop.
>
> -- 
> Andy Robinson, Seventh String Software, www.seventhstring.com 

Andy Robinson wrote:
> Replying to my own post, a slightly inelegant partial solution has
> occurred to me, which would be perfectly practical where there are
> only a small number of possible n's, none of them too huge. (e.g. n
> is a power of 2 from 2^1 to 2^20, say, which would do for me).
> 
> Simply, write a test program to pre-compute suitable lists of
> loop-start-points, and hardwire these 20 lists into the program!
> 
> But if anyone has a more general and/or more elegant solution, I'd
> still like to know.
> 
> Thanks,
> Andy Robinson, Seventh String Software, www.seventhstring.com

If the real and imaginary arrays are contiguous, they can be considered 
to be a single two-dimensional array. By exchanging the array indices, 
the job is done. Why move data?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

in article JoydnagfEoeY0aXfRVn-tw@rcn.net, Jerry Avins at jya@ieee.org wrote
on 03/16/2005 10:08:

> Andy Robinson wrote:
>> Replying to my own post, a slightly inelegant partial solution has
>> occurred to me, which would be perfectly practical where there are
>> only a small number of possible n's, none of them too huge. (e.g. n
>> is a power of 2 from 2^1 to 2^20, say, which would do for me).
>> 
>> Simply, write a test program to pre-compute suitable lists of
>> loop-start-points, and hardwire these 20 lists into the program!
>> 
>> But if anyone has a more general and/or more elegant solution, I'd
>> still like to know.
>> 
>> Thanks,
>> Andy Robinson, Seventh String Software, www.seventhstring.com
> 
> If the real and imaginary arrays are contiguous, they can be considered
> to be a single two-dimensional array. By exchanging the array indices,
> the job is done. Why move data?

he might be trying to plug the data into an existing piece of software
(perhaps and FFT) that has a "complex" type, and an array of complex would
have the real followed by the imag for each complex element.

that was never a problem for me in the past, because i had some
pre-processing before filling the FFT buffer.  either i was windowing from
the input buffer and/or pre-bit reversing.  or in the wavetable synthesis
case, i was extracting a single cycle out of the input stream (and my FFT
buffer wasn't too big, either 256 or 512 or 1024).

but the FFT software i have used (including my own kludged version) expected
its complex input to have interleaved real and imag parts.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

Jerry Avins wrote:

> Andy Robinson wrote:
>> Replying to my own post, a slightly inelegant partial solution has
>> occurred to me, which would be perfectly practical where there are
>> only a small number of possible n's, none of them too huge. (e.g. n
>> is a power of 2 from 2^1 to 2^20, say, which would do for me).
>> 
>> Simply, write a test program to pre-compute suitable lists of
>> loop-start-points, and hardwire these 20 lists into the program!
>> 
>> But if anyone has a more general and/or more elegant solution, I'd
>> still like to know.
>> 
>> Thanks,
>> Andy Robinson, Seventh String Software, www.seventhstring.com
> 
> If the real and imaginary arrays are contiguous, they can be
> considered to be a single two-dimensional array. By exchanging the
> array indices, the job is done. Why move data?
> 
> Jerry

Transferring data between already existing bodies of code which use
different formats. Massaging the data is easier than rewriting the
code.

-- 
Andy Robinson, Seventh String Software, www.seventhstring.com

"Andy Robinson" <andy@seventhstring.com> wrote in message
news:d196on$kl$1$8300dec7@news.demon.co.uk...
> This seems like an obvious question but I've Googled around without
> finding the answer.
>
> Given an array containing n real values followed by n imaginaries, is
> there a way of swapping them around in-place so as to end up with an
> array of n complex numbers? Without allocating an extra buffer.
>
> R0 R1 R2 R3 I0 I1 I2 I3
> becomes
> R0 I0 R1 I1 R2 I2 R3 I3

Here is one 'algorithm' I thought of...I don't claim it to be the most
efficient (but you can figure out if it is).
I'm making an assumption here that the 2 buffers are contiguous in memory
(since I'm talking about pointer notation).
I'm sure there is a way to modify or adapt this if this cannot be assumed.
I'm also assuming you have a power of 2 points

Start with a pointer to the imaginary buffer (position 0), and a pointer to
the real buffer (position 1).
Keep swapping data points (step your imaginary buffer in steps of 1 and your
real buffer in steps of 2). Note that you will encroach into your imaginary
buffer for the second half of your operations.
For example,
Take I0 and swap with R1.
Take I1 and swap with R3
Take I2 and swap with R5
..
Take I4 and swap with R3 (this is because R3 got swapped with I1 earlier and
since the real pointer has a step size of 2, you are now in the imaginary
area).

At the end of this operation, you will have all you imaginary components in
the right locations. And my assertion is that all the real samples are in a
bit reversed order in your buffer (consider it as one large buffer) - this
only works for a power of 2.

So, if you assume 8 real and 8 imaginary samples to start with...
r0 i0 r2 i1 r4 i2 r6 i3 r1 i4 r5 i5 r3 i6 r7 i7

Now couldn't you just use a standard algorithm to correct the bit reversed
order of the real samples and then you have the complex pairs?

Cheers
Bhaskar

> Clearly we can pick any starting location, identify the place where
> the number we find there ought to go, take it there and repeat with
> the number we find in this new location, until we find ourselves back
> at the starting location we chose.
>
> The entire interleave can be carried out by a number of loops like
> this, but how to select a suitable set of starting points? (without
> allocating an extra buffer to keep track of what we've done). We can
> tell when we are finished by counting how many moves we've done in
> total. The difficulty is when we are not finished, selecting a
> starting point which has not been touched yet by a previous loop.
>
> -- 
> Andy Robinson, Seventh String Software, www.seventhstring.com

Bhaskar Thiagarajan wrote:

> "Andy Robinson" <andy@seventhstring.com> wrote in message
> news:d196on$kl$1$8300dec7@news.demon.co.uk...
>> This seems like an obvious question but I've Googled around without
>> finding the answer.
>>
>> Given an array containing n real values followed by n imaginaries,
>> is there a way of swapping them around in-place so as to end up
>> with an array of n complex numbers? Without allocating an extra
>> buffer.
>>
>> R0 R1 R2 R3 I0 I1 I2 I3
>> becomes
>> R0 I0 R1 I1 R2 I2 R3 I3
> 
> Here is one 'algorithm' I thought of...I don't claim it to be the
> most efficient (but you can figure out if it is).
> I'm making an assumption here that the 2 buffers are contiguous in
> memory (since I'm talking about pointer notation).
> I'm sure there is a way to modify or adapt this if this cannot be
> assumed. I'm also assuming you have a power of 2 points
> 
> Start with a pointer to the imaginary buffer (position 0), and a
> pointer to the real buffer (position 1).
> Keep swapping data points (step your imaginary buffer in steps of 1
> and your real buffer in steps of 2). Note that you will encroach
> into your imaginary buffer for the second half of your operations.
> For example,
> Take I0 and swap with R1.
> Take I1 and swap with R3
> Take I2 and swap with R5
> ..
> Take I4 and swap with R3 (this is because R3 got swapped with I1
> earlier and since the real pointer has a step size of 2, you are now
> in the imaginary area).
> 
> At the end of this operation, you will have all you imaginary
> components in the right locations. And my assertion is that all the
> real samples are in a bit reversed order in your buffer (consider it
> as one large buffer) - this only works for a power of 2.

This is very ingenious, thank you - I'll take your word for it about
the bit-reversed order!

However, I don't want to seem ungrateful, but it's surely not optimal
as some elements get moved more than once, whereas if the interleave
is done as a number of closed-loop-moves as I mentioned originally,
each element is moved only once.

Given that I'm happy with powers-of-2 only, I probably will in fact
precompute a list of loop-start-points for each power.

-- 
Andy Robinson, Seventh String Software, www.seventhstring.com

"Andy Robinson" <andy@seventhstring.com> wrote in message
news:d1bquv$4o2$1$8302bc10@news.demon.co.uk...
> Bhaskar Thiagarajan wrote:
>
> > "Andy Robinson" <andy@seventhstring.com> wrote in message
> > news:d196on$kl$1$8300dec7@news.demon.co.uk...
> >> This seems like an obvious question but I've Googled around without
> >> finding the answer.
> >>
> >> Given an array containing n real values followed by n imaginaries,
> >> is there a way of swapping them around in-place so as to end up
> >> with an array of n complex numbers? Without allocating an extra
> >> buffer.
> >>
> >> R0 R1 R2 R3 I0 I1 I2 I3
> >> becomes
> >> R0 I0 R1 I1 R2 I2 R3 I3
> >
> > Here is one 'algorithm' I thought of...I don't claim it to be the
> > most efficient (but you can figure out if it is).
> > I'm making an assumption here that the 2 buffers are contiguous in
> > memory (since I'm talking about pointer notation).
> > I'm sure there is a way to modify or adapt this if this cannot be
> > assumed. I'm also assuming you have a power of 2 points
> >
> > Start with a pointer to the imaginary buffer (position 0), and a
> > pointer to the real buffer (position 1).
> > Keep swapping data points (step your imaginary buffer in steps of 1
> > and your real buffer in steps of 2). Note that you will encroach
> > into your imaginary buffer for the second half of your operations.
> > For example,
> > Take I0 and swap with R1.
> > Take I1 and swap with R3
> > Take I2 and swap with R5
> > ..
> > Take I4 and swap with R3 (this is because R3 got swapped with I1
> > earlier and since the real pointer has a step size of 2, you are now
> > in the imaginary area).
> >
> > At the end of this operation, you will have all you imaginary
> > components in the right locations. And my assertion is that all the
> > real samples are in a bit reversed order in your buffer (consider it
> > as one large buffer) - this only works for a power of 2.
>
> This is very ingenious, thank you - I'll take your word for it about
> the bit-reversed order!
>
> However, I don't want to seem ungrateful, but it's surely not optimal
> as some elements get moved more than once, whereas if the interleave
> is done as a number of closed-loop-moves as I mentioned originally,
> each element is moved only once.

Yes - there are redundant moves, but they are essential if you want to end
up with the bit reversed positions for the real samples which will help your
second pass simpler. Your closed-loop moves will be more optimal in moves
but will be more complex in the logic.
Like I already mentioned, my proposed solution was by no means the most
optimal but was perhaps reasonably elegant and simple to implement (I'm
actually unware of an in-place bit reversal algorithm which is essential to
complete the solution, but I presume it's been done before). You get to
choose where you want to make the trade-offs.

Cheers
Bhaskar



>
> Given that I'm happy with powers-of-2 only, I probably will in fact
> precompute a list of loop-start-points for each power.
>
> -- 
> Andy Robinson, Seventh String Software, www.seventhstring.com