[Scilab-users] circshift() : Scilab Enhancement Proposal

classic Classic list List threaded Threaded
18 messages Options
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|

[Scilab-users] circshift() : Scilab Enhancement Proposal

Dear co-scilabers,

After the wish reported at http://bugzilla.scilab.org/7293 in 2010,
some cshift() function was proposed on the FileExchange at
http://fileexchange.scilab.org/toolboxes/161000 to provide a way
to circularly shift the rows or columns of a matrix or an hypermatrix.

In order to include this basic but non-trivial feature in Scilab 6.1,
a Scilab Enhancement Proposal is posted on review at
https://codereview.scilab.org/#/c/19625/

Proposed features are described in the help page in PDF format in
attachment.

Every comment is welcome.

Best regards
Samuel Gougeon


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users

circshift.pdf (64K) Download Attachment
Antoine Monmayrant Antoine Monmayrant
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

Hi Samuel,


Thanks a lot for this nice SEP.
I have a couple of comments:

1) I think I should be good to also show some multidimensional examples using "shifts" and using both "shifts" and "dims". Sometimes in the scilab documentation, the user is served with examples only covering the most basic usage and not the advanced one with N optional arguments.

2) For multidimentional cshift, the order of the shifts (for example shift  by N along the lines than shift by M along the columns or the other way round) is key, right? Inverting the order would give a different result, right? Should this be specified in the SEP:

circshift(A, shifts) first circularly shifts indices of A rows by shifts(1), then the indices of A columns by shifts(2), then indices of A layers by shifts(3), etc.

Cheers,

Antoine

(& Happy New Year to all!)

Le 23/12/2017 à 19:06, Samuel Gougeon a écrit :
Dear co-scilabers,

After the wish reported at http://bugzilla.scilab.org/7293 in 2010,
some cshift() function was proposed on the FileExchange at
http://fileexchange.scilab.org/toolboxes/161000 to provide a way
to circularly shift the rows or columns of a matrix or an hypermatrix.

In order to include this basic but non-trivial feature in Scilab 6.1,
a Scilab Enhancement Proposal is posted on review at
https://codereview.scilab.org/#/c/19625/

Proposed features are described in the help page in PDF format in attachment.

Every comment is welcome.

Best regards
Samuel Gougeon



_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

Hello Antoine,

Thanks for your time to have read this proposal and comment it.

I am afraid i don't catch your first point. As far as i understand your suggestion, the last existing example with an hypermatrix of texts already fulfills it.
For my part, in examples, i think it is better to show results as often as possible, not only the code. Since there is presently no way to display examples by default in a fold way (at least in the native Scilab help browser/viewer, with a "+/-" clickable switch), this makes quite long pages that requires to be scrolled a lot. By the way, as soon as hypermatrices are involved, displayed results are still more lengthy. So, in my opinion, there is a compromise.

About the order of multiple crossed or parallel or mixed shifts: no, the order does not matter. One gets the same result whatever the order is.

Happy new year 2018 to you and to every scilaber.
Have nice projects and involvements with Scilab and others.

Best wishes
Samuel

Le 03/01/2018 à 09:09, antoine monmayrant a écrit :

Hi Samuel,


Thanks a lot for this nice SEP.
I have a couple of comments:

1) I think I should be good to also show some multidimensional examples using "shifts" and using both "shifts" and "dims". Sometimes in the scilab documentation, the user is served with examples only covering the most basic usage and not the advanced one with N optional arguments.

2) For multidimentional cshift, the order of the shifts (for example shift  by N along the lines than shift by M along the columns or the other way round) is key, right? Inverting the order would give a different result, right? Should this be specified in the SEP:

circshift(A, shifts) first circularly shifts indices of A rows by shifts(1), then the indices of A columns by shifts(2), then indices of A layers by shifts(3), etc.

Cheers,

Antoine

(& Happy New Year to all!)

Le 23/12/2017 à 19:06, Samuel Gougeon a écrit :
Dear co-scilabers,

After the wish reported at http://bugzilla.scilab.org/7293 in 2010,
some cshift() function was proposed on the FileExchange at
http://fileexchange.scilab.org/toolboxes/161000 to provide a way
to circularly shift the rows or columns of a matrix or an hypermatrix.

In order to include this basic but non-trivial feature in Scilab 6.1,
a Scilab Enhancement Proposal is posted on review at
https://codereview.scilab.org/#/c/19625/

Proposed features are described in the help page in PDF format in attachment.

Every comment is welcome.

Best regards
Samuel Gougeon



_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users



_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users



_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Rafael Guerra Rafael Guerra
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

In reply to this post by Antoine Monmayrant

Samuel,

 

As requested, some further feedback on circshift:

 

  • The proposed syntax seems to be compatible with Matlab’s circshift while adding extra functionality, which is very positive

 

  • To add to the wish list: if the input matrix represents a regularly sampled function, it would be useful to have in Scilab a generalization of circshift allowing non-integer shifts, also to have option for non-circular shifts and for padding with zeros

 

Best Wishes for 2018!

 

Rafael

 

 

Le 23/12/2017 à 19:06, Samuel Gougeon a écrit :

Dear co-scilabers,

After the wish reported at
http://bugzilla.scilab.org/7293
in 2010,
some cshift() function was proposed on the FileExchange at
http://fileexchange.scilab.org/toolboxes/161000 to provide a way
to circularly shift the rows or columns of a matrix or an hypermatrix.

In order to include this basic but non-trivial feature in Scilab 6.1,
a Scilab Enhancement Proposal is posted on review at
https://codereview.scilab.org/#/c/19625/

Proposed features are described in the help page in PDF format in attachment.

Every comment is welcome.

Best regards
Samuel Gougeon




_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users

 


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

Thanks for your comments, Rafael.
I am answering in the body:

Le 03/01/2018 à 16:00, Rafael Guerra a écrit :

Samuel,

 

As requested, some further feedback on circshift:

 

  • The proposed syntax seems to be compatible with Matlab’s circshift while adding extra functionality, which is very positive

 

  • To add to the wish list: if the input matrix represents a regularly sampled function, it would be useful to have in Scilab a generalization of circshift allowing non-integer shifts,

As far as i understand, you are addressing here an interpolation feature rather than an indices-shifting one.
IMO, this is a job much closer to existing interp#() functions than to circshift(). Interpolations modes usually propose options to process edges, and other ones to chose an interpolation mode (linear, splines ,etc).
This is far beyond and out of the purpose of circshift(), that does not change values, just indices.

  • also to have option for non-circular shifts and for padding with zeros

Something like circshift(), without circ ;)
Padding is presently proposed throught resize_matrix(). But indeed, it does not propose left or top padded insertions.
This will become easy with circshift() as it is presently proposed. Example:

--> m = grand(3,4,"uin",0,9)
 m  =
   2.   5.   9.   3.
   2.   4.   5.   5.
   4.   1.   8.   5.

--> circshift(resize_matrix(m, [5,7]),[1,2])
 ans  =
   0.   0.   0.   0.   0.   0.   0.
   0.   0.   2.   5.   9.   3.   0.
   0.   0.   2.   4.   5.   5.   0.
   0.   0.   4.   1.   8.   5.   0.
   0.   0.   0.   0.   0.   0.   0.

The main resize_matrix() syntax is

resMat = resize_matrix(mat, nbRows, nbCols)

Specifying a vector of 2 components instead of a scalar for either nbrows or nbcols or both would enable specifying margins on both sides for each direction, instead of the new required sizes.
IMO, this would be an improvement for resize_matrix() rather than a circshift() extension.
Don't you think so?

Best regards
Samuel


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

In reply to this post by Rafael Guerra
Hello Rafael,

Le 03/01/2018 à 16:00, Rafael Guerra a écrit :

Samuel,

 

As requested, some further feedback on circshift:

 .../...

  • To add to the wish list: if the input matrix represents a regularly sampled function, it would be useful to have in Scilab a generalization of circshift allowing non-integer shifts, also to have option for non-circular shifts and for padding with zeros

To go on about resize_matrix() , padding, and shifting without wrapping:
Specifying a (N>1 x 2) matrix of positive (pad) or negative (trim) margins resizing
would be simple.
Padding with other default elements for non-numerical arrays, or with a chosen
value, is already enabled.
Possible new syntaxes and examples of usages:

resMat = resize_matrix(mat, frameWidth)
resMat = resize_matrix(mat, frameWidth, ..)

m = [
  6 -7 -1 -2
 -6  0 -2 -5
 -5  4 -1  8
  ];

// shift without extension nor wrapping:
resize_matrix(m, [0 0 ; -1 1])
ans =
  -7 -1 -2  0
   0 -2 -5  0
   4 -1  8  0

// Another case without extensions nor wrapping:
resize_matrix(m, [1 -1 ; 2 -2])
ans = 
0  0  0  0 
0  0  6 -7 
0  0 -6  0 

// More general
resize_matrix(m, [2 1 ; 1 -1])
ans = 
0  0  0  0 
0  0  0  0 
0  6 -7 -1 
0 -6  0 -2 
0 -5  4 -1 
0  0  0  0 


Is it the kind of features you were thinking about?

IMO, there is no need to implement this in another specific function, because these features are just particular cases or resizing, with a simple syntax allowing to crop borders as well.

Best regards
Samuel


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Rafael Guerra Rafael Guerra
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

Hi Samuel,

 

The functionality is very nice but the syntax proposed is maybe a bit complicated?

It would be easier to combine ‘newSizes’ with a new ‘shift’ argument (but with no wrapping as proposed in circshift).

For example:

 

 m  =
   2.   5.   9.   3.
   2.   4.   5.   5.
   4.   1.   8.   5.

 

resize_matrix(m, newSizes=[5 7], shift=[1 2])

 ans  =
   0.   0.   0.   0.   0.   0.   0.
   0.   0.   2.   5.   9.   3.   0.
   0.   0.   2.   4.   5.   5.   0.
   0.   0.   4.   1.   8.   5.   0.
   0.   0.   0.   0.   0.   0.   0.

 

resize_matrix(m, newSizes=[-1 -1], shift=[-1 -2])

 ans  =

   5.   5.   0.   0.
   8.   5.   0.   0.
   0.   0.   0.   0. 

 

 

Regarding extending circshift() to non-integers I had in mind n-dimensional matrices and the discrete Fourier transform.

These matrices could represent regularly sampled 1D time signals, or 2D/3D spatial functions, etc.

In this context the shift theorem gives a specific meaning to the circular shifts of the input signals (corresponding to linear phase shifts in their spectrum).

 

Regards,

Rafael

 

From: users [mailto:[hidden email]] On Behalf Of Samuel Gougeon
Sent: Tuesday, January 09, 2018 8:26 PM
To: Users mailing list for Scilab <[hidden email]>
Subject: Re: [Scilab-users] circshift() : Scilab Enhancement Proposal

 

Hello Rafael,

To go on about resize_matrix() , padding, and shifting without wrapping:
Specifying a (N>1 x 2) matrix of positive (pad) or negative (trim) margins resizing
would be simple.
Padding with other default elements for non-numerical arrays, or with a chosen
value, is already enabled.
Possible new syntaxes and examples of usages:

 
resMat = resize_matrix(mat, frameWidth)
resMat = resize_matrix(mat, frameWidth, ..)
 
m = [
  6 -7 -1 -2
 -6  0 -2 -5
 -5  4 -1  8
  ];
 
// shift without extension nor wrapping:
resize_matrix(m, [0 0 ; -1 1])
ans =
  -7 -1 -2  0
   0 -2 -5  0
   4 -1  8  0
 
// Another case without extensions nor wrapping:
resize_matrix(m, [1 -1 ; 2 -2])
ans = 
0  0  0  0 
0  0  6 -7 
0  0 -6  0 
 
// More general
resize_matrix(m, [2 1 ; 1 -1])
ans = 
0  0  0  0 
0  0  0  0 
0  6 -7 -1 
0 -6  0 -2 
0 -5  4 -1 
0  0  0  0 
 
 

Is it the kind of features you were thinking about?

IMO, there is no need to implement this in another specific function, because these features are just particular cases or resizing, with a simple syntax allowing to crop borders as well.

Best regards
Samuel


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

Hello Rafael,

Le 10/01/2018 à 00:01, Rafael Guerra a écrit :

Hi Samuel,

 

.../...

 

Regarding extending circshift() to non-integers I had in mind n-dimensional matrices and the discrete Fourier transform.

These matrices could represent regularly sampled 1D time signals, or 2D/3D spatial functions, etc.

In this context the shift theorem gives a specific meaning to the circular shifts of the input signals (corresponding to linear phase shifts in their spectrum).


Using fractional shifts means that we somewhat address some frequencies
higher than the sampling one. Then, as expected, if such a feature is
implemented through the DFT, and unless the input signal is
* a truly periodic one
* sampled over an integer number of its period,
which are very restrictive conditions, we will face issues such as the Gibb
artefact, deserving or even demanding some damping window options, etc.

This is far beyond the main purpose of circshift() whose elementary job misses for years now.
We would go then into signal processing, with its usual complications,
only applicable to arrays of real or complex numbers, while circshift() is
basically applicable to all arrays of any datatype.

To me, your proposal to extend circshift() to fractional shifts needs some
further analysis, to compare several possible implementations.
It could make an additional SEP with its own new options, after merging
the basic but very expected circshift().

Using the DFT to interpolate input data has the main advantage to not be
a local method. As a trade-off, it yields some artefacts, at least with a simple
implementation as provided herebelow.
Please do not hesitate to go on with it. I have not tried to recover the undamped
shifted signal after using some damping window to get ride of Gibb.

Using classical local interpolations -- linear or splined ones -- is also meaningful
and applicable only to real or complex numerical data.

A benchmark could be set to compare performances of DFT versus local interpolations,
iterating small fractional shifts summed to an integer, and measuring the distance
of the result to the true expected one (after an integer shift).
I let you do that and build your extension proposal.

Cheers
Samuel


// Fractional circshift: tests
n = 100;
sig = sin(linspace(0, 2.5, n)); // Built discontinuity from 2.5=>0
clf
subplot(1, 3, 1)
plot(sig)
title("Input 1D signal", "fontsize",3);

subplot(1, 3, 2)
v = frac_shift(sig, 35);
plot(real(v))
title("Integer shift = 35", "fontsize",3);

subplot(1, 3, 3)
v = frac_shift(sig, 35.4);  // fractional shift = 35.4
plot(real(v))
title("Fractional shift = 35.4", "fontsize",3);
gca().tight_limits="on";
// As expected, we get some Gibb artefact oscillations near the
// discontinuity. Avoiding them required to damp wings of the input
// signal in order to damp the discontinuity, requiring to use a
// damping window and profile.

function v = frac_shift(x, n)
    // x: 1D signal
    // n: shift, in decimal number of samples
    // v: x shifted by i samples
    N = length(x)
    sp = fft(x, -1).';
    frequencies = (floor(-(N-1)/2):floor((N-1)/2))/N
    c = exp(2*%pi*%i*n*frequencies).';
    shifted_sp = ifftshift(fftshift(sp).*c);
    v = fft(shifted_sp,1);
    mprintf("%5.2f  max(abs(imag(shifted sig)))= %f\n", n, max(abs(imag(v))));
endfunction



_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Rafael Guerra Rafael Guerra
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

Hi Samuel,

The implementation below of the circular fractional shift function seems to suffer from less endpoints’ artefacts.

// START OF CODE
// Circular fractional shift (R.Guerra, 01-Jun-2018)

function v=cfshift(y, s)
    // y: 1D series of real values
    // s: shift, decimal number of samples
    // v: y series shifted by s samples
    N0 = length(y);
    y2 = [y y($:-1:1)]; // make input even and continuous
    N = length(y2);
    m = N/2;
    dw = -%i*2*%pi/N;
    ix1 = 1:m;
    ix = [0, ix1, -ix1(m-1:-1:1)];
    s = modulo(s,N0);
    lph = exp(ix*dw*s);
    v0 = real((ifft(fft(y2).*lph)));
    n0 = floor(s);
    if n0>=0 then
       v = [v0(N0+1:N0+n0) v0(n0+1:N0)];
    else
       v = [v0(1:N0+n0) v0(N+n0+1:N)];
    end
endfunction

clf
n = 30;  // number of input samples
x = 1:n;  // domain of the series, with unit sampling rate
sn = -33;  // ex.1: negative integer shift (modulo(sn,n) = -3)
sp = 10.5; // ex.2: positive fractional shift
y = cos(1.8*%pi*(x-10)/n); // ex. of input series with discontinuous at endpoints
vi = cfshift(y, sn);  
vf = cfshift(y, sp);
plot(x,y,'blacko',x,y,'black--',x,vi,'bo',x,vi,'b--',x,vf,'ro',x,vf,'r--');
xgrid
title("Original series with circular integer shift = " + string(sn) + " (blue) and circular fractional shift = " + string(sp) +" (red)", "fontsize",4);
gca().data_bounds = [0.5,-1.1;n+0.5,1.1]
gca().tight_limits="on";

// END OF CODE


Not sure if this is the best way to implement this.
Also, it requires generalization to complex numbers and multi-dimensions.

Regards,
Rafael

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users

fractional_circular_shifts_1d.png (43K) Download Attachment
Rafael Guerra Rafael Guerra
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal


The previous fractional shift code was still not handling properly the endpoints.
Herein an improvement.
Fourier is still used but the sample laying between end and start points is interpolated.

// START OF CODE
// Circular fractional shift (R.Guerra, rev1, 02-Jun-2018)

function v=cfshift(y, s)
    // y: 1D series values
    // s: shift, decimal number of samples
    // v: y series shifted by s samples
    N0 = length(y);
    y2 = [y y($:-1:1)]; // make input even and continuous
    N = length(y2);
    m = N/2;
    dw = -%i*2*%pi/N;
    ix1 = 1:m;
    ix = [0, ix1, -ix1(m-1:-1:1)];
    s = modulo(s,N0);
    lph = exp(ix*dw*s);
    v0 = real((ifft(fft(y2).*lph)));
    n0 = floor(s);
    xi = s - n0;
    yi = y(1) + xi*(y($)-y(1)); //interpolates sample between end and start
    if n0>=0 then
       v = [v0(N0+1:N0+n0) yi v0(n0+2:N0)];
    else
       v = [v0(1:N0+n0) yi v0(N+n0+2:N)];
    end
endfunction

clf
n = 30;  // number of input samples
x = 1:n;  // domain of the series, with unit sampling rate
sn = -33;  // ex.1: negative integer shift (modulo(sn,n) = -3)
sp = 10.5; // ex.2: positive fractional shift
y = cos(1.8*%pi*(x-10)/n); // input series, discontinuous at endpoints

vi = cfshift(y, sn);  
vf = cfshift(y, sp);

plot(x,y,'blacko',x,y,'black--',x,vi,'bo',x,vi,'b--',x,vf,'ro',x,vf,'r--');
xgrid
title("Original series (black), with circular integer shift = " + string(sn) + " (blue) and circular fractional shift = " + string(sp) +" (red)", "fontsize",4);
gca().data_bounds = [0.5,-1.1;n+0.5,1.1]
gca().tight_limits="on";

// END OF CODE

Regards,
Rafael

_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users

fractional_circular_shifts_1d_rev1.png (53K) Download Attachment
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

In reply to this post by Rafael Guerra
Hello Rafael,

I did not remember this symetrization trick that you use to restore continuous boundaries and so avoid the noise-making jump.
It is very efficient. Great!

I don't see any reason that could make this trick failing with complex numbers:
Making the signal even makes its spectrum even, whatever is the signal, real or complex.
So, the very same algorithm shall work as well for complex data.

Extension to N-Dimension should be OK as well with the fft(., ., selection) syntax, and a loop other the selected direction.

May be because the slope is still discontinuous, there is still a tiny artefact after shifting.
This may invite to still try with a damping window, in comparison with the symetrization.
Damping makes the signal and its derivative continuous across limits.

I am answering to your next message by replying to it.

Best regards
Samuel

Le 01/06/2018 à 17:56, Rafael Guerra a écrit :
Hi Samuel,

The implementation below of the circular fractional shift function seems to suffer from less endpoints’ artefacts.

// START OF CODE
// Circular fractional shift (R.Guerra, 01-Jun-2018)

function v=cfshift(y, s)
    // y: 1D series of real values
    // s: shift, decimal number of samples
    // v: y series shifted by s samples
    N0 = length(y);
    y2 = [y y($:-1:1)]; // make input even and continuous
    N = length(y2);
    m = N/2;
    dw = -%i*2*%pi/N;
    ix1 = 1:m;
    ix = [0, ix1, -ix1(m-1:-1:1)];
    s = modulo(s,N0);
    lph = exp(ix*dw*s);
    v0 = real((ifft(fft(y2).*lph)));
    n0 = floor(s);
    if n0>=0 then
       v = [v0(N0+1:N0+n0) v0(n0+1:N0)];
    else
       v = [v0(1:N0+n0) v0(N+n0+1:N)];
    end
endfunction

clf
n = 30;  // number of input samples
x = 1:n;  // domain of the series, with unit sampling rate
sn = -33;  // ex.1: negative integer shift (modulo(sn,n) = -3)
sp = 10.5; // ex.2: positive fractional shift
y = cos(1.8*%pi*(x-10)/n); // ex. of input series with discontinuous at endpoints
vi = cfshift(y, sn);  
vf = cfshift(y, sp);
plot(x,y,'blacko',x,y,'black--',x,vi,'bo',x,vi,'b--',x,vf,'ro',x,vf,'r--');
xgrid
title("Original series with circular integer shift = " + string(sn) + " (blue) and circular fractional shift = " + string(sp) +" (red)", "fontsize",4);
gca().data_bounds = [0.5,-1.1;n+0.5,1.1]
gca().tight_limits="on";

// END OF CODE


Not sure if this is the best way to implement this.
Also, it requires generalization to complex numbers and multi-dimensions.

Regards,
Rafael


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users



_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

In reply to this post by Rafael Guerra
Rafael,

To me, this attempt looks not legitimate.
Indeed, the true original signal HAS a steep jump across its edges.
So, the best algorithm should  shift the signal and keep this big slope
from one sample to the next. The jump is at least as steep as from
one sample to the next (and likely steeper). It must not be broadened.
There is no reason to interpolate and then decrease the slope.
Is there?

IMO, hybridating DFT and interpolation is not promising, and
DFT looks more powerful. So, to me, now the question is mainly:
with symetrization, versus with damping.

Read you soon
Samuel

Le 02/06/2018 à 15:23, Rafael Guerra a écrit :
The previous fractional shift code was still not handling properly the endpoints.
Herein an improvement.
Fourier is still used but the sample laying between end and start points is interpolated.

// START OF CODE
// Circular fractional shift (R.Guerra, rev1, 02-Jun-2018)

function v=cfshift(y, s)
    // y: 1D series values
    // s: shift, decimal number of samples
    // v: y series shifted by s samples
    N0 = length(y);
    y2 = [y y($:-1:1)]; // make input even and continuous
    N = length(y2);
    m = N/2;
    dw = -%i*2*%pi/N;
    ix1 = 1:m;
    ix = [0, ix1, -ix1(m-1:-1:1)];
    s = modulo(s,N0);
    lph = exp(ix*dw*s);
    v0 = real((ifft(fft(y2).*lph)));
    n0 = floor(s);
    xi = s - n0;
    yi = y(1) + xi*(y($)-y(1)); //interpolates sample between end and start
    if n0>=0 then
       v = [v0(N0+1:N0+n0) yi v0(n0+2:N0)];
    else
       v = [v0(1:N0+n0) yi v0(N+n0+2:N)];
    end
endfunction

clf
n = 30;  // number of input samples
x = 1:n;  // domain of the series, with unit sampling rate
sn = -33;  // ex.1: negative integer shift (modulo(sn,n) = -3)
sp = 10.5; // ex.2: positive fractional shift
y = cos(1.8*%pi*(x-10)/n); // input series, discontinuous at endpoints

vi = cfshift(y, sn);  
vf = cfshift(y, sp);

plot(x,y,'blacko',x,y,'black--',x,vi,'bo',x,vi,'b--',x,vf,'ro',x,vf,'r--');
xgrid
title("Original series (black), with circular integer shift = " + string(sn) + " (blue) and circular fractional shift = " + string(sp) +" (red)", "fontsize",4);
gca().data_bounds = [0.5,-1.1;n+0.5,1.1]
gca().tight_limits="on";

// END OF CODE

Regards,
Rafael


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users



_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Rafael Guerra Rafael Guerra
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

Samuel,

 

The idea and the implementation of the end-points interpolation is that this is done on the input data (big slope), not on the FFT output. Maybe be it needs some further work. Tbc.

 

Regards,

Rafael

 

From: users [mailto:[hidden email]] On Behalf Of Samuel Gougeon
Sent: Wednesday, June 06, 2018 9:35 PM
To: Users mailing list for Scilab <[hidden email]>
Subject: Re: [Scilab-users] circshift() : Scilab Enhancement Proposal

 

Rafael,

To me, this attempt looks not legitimate.
Indeed, the true original signal HAS a steep jump across its edges.
So, the best algorithm should  shift the signal and keep this big slope
from one sample to the next
. The jump is at least as steep as from
one sample to the next (and likely steeper). It must not be broadened.
There is no reason to interpolate and then decrease the slope.
Is there?

IMO, hybridating DFT and interpolation is not promising, and
DFT looks more powerful. So, to me, now the question is mainly:
with symetrization, versus with damping.

Read you soon
Samuel

Le 02/06/2018 à 15:23, Rafael Guerra a écrit :

 
The previous fractional shift code was still not handling properly the endpoints.
Herein an improvement.
Fourier is still used but the sample laying between end and start points is interpolated.
 
// START OF CODE
// Circular fractional shift (R.Guerra, rev1, 02-Jun-2018)
 
function v=cfshift(y, s)
    // y: 1D series values
    // s: shift, decimal number of samples
    // v: y series shifted by s samples
    N0 = length(y);
    y2 = [y y($:-1:1)]; // make input even and continuous
    N = length(y2);
    m = N/2;
    dw = -%i*2*%pi/N;
    ix1 = 1:m;
    ix = [0, ix1, -ix1(m-1:-1:1)];
    s = modulo(s,N0);
    lph = exp(ix*dw*s);
    v0 = real((ifft(fft(y2).*lph)));
    n0 = floor(s);
    xi = s - n0;
    yi = y(1) + xi*(y($)-y(1)); //interpolates sample between end and start
    if n0>=0 then
       v = [v0(N0+1:N0+n0) yi v0(n0+2:N0)];
    else
       v = [v0(1:N0+n0) yi v0(N+n0+2:N)];
    end
endfunction
 
clf
n = 30;  // number of input samples
x = 1:n;  // domain of the series, with unit sampling rate
sn = -33;  // ex.1: negative integer shift (modulo(sn,n) = -3)
sp = 10.5; // ex.2: positive fractional shift
y = cos(1.8*%pi*(x-10)/n); // input series, discontinuous at endpoints
 
vi = cfshift(y, sn);  
vf = cfshift(y, sp);
 
plot(x,y,'blacko',x,y,'black--',x,vi,'bo',x,vi,'b--',x,vf,'ro',x,vf,'r--');
xgrid
title("Original series (black), with circular integer shift = " + string(sn) + " (blue) and circular fractional shift = " + string(sp) +" (red)", "fontsize",4);
gca().data_bounds = [0.5,-1.1;n+0.5,1.1]
gca().tight_limits="on";
 
// END OF CODE
 
Regards,
Rafael




_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users

 


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Rafael Guerra Rafael Guerra
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

Noting also that between the endpoints of the DFT periodic input, there is the interval of one sample.

 

From: users [mailto:[hidden email]] On Behalf Of Rafael Guerra
Sent: Wednesday, June 06, 2018 10:19 PM
To: Users mailing list for Scilab <[hidden email]>
Subject: Re: [Scilab-users] circshift() : Scilab Enhancement Proposal

 

Samuel,

 

The idea and the implementation of the end-points interpolation is that this is done on the input data (big slope), not on the FFT output. Maybe be it needs some further work. Tbc.

 

Regards,

Rafael


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

In reply to this post by Rafael Guerra
>Samuel,
>
>The idea and the implementation of the end-points interpolation is that
>this is done on the input data (big slope), not on the FFT output.

This is clear

>Maybe be it needs some further work. Tbc.

I don't think so.

>Noting also that between the endpoints of the DFT periodic input, there is the interval of one sample.

That is to say: Let u(1:$) be the original signal.
Since it is virtually periodic, the FFT sees u($+1)=u(1).
Do we agree about this?

Then: Do we agree on that the |slope| across the shifted edges
of u is necessarily greater or equal to |u($)-u(1)|/1 ?
_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Rafael Guerra Rafael Guerra
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

Hi Samuel,

 

Fyi, many DFT references recommend averaging the values at endpoints and discontinuities in general. See for instance:

 

Briggs, W. L. and V. E. Henson [1005] The DFT: an owner's manual for the Discrete Fourier Transform, SIAM, Philadelphia.

 

I think my solution is simple and it looks harmless to me. At least the results look reasonable for different amounts of fractional shifts tested.

But I will keep studying the subject.

Maybe some expert on the matter can jump in.

 

Note sure about your last question as many scenarios can be thought of, of continuous functions with discontinuities and their sampled versions.

I can think of cases where the slope can be < |u($)-u(1)|/1

 

Regards,

Rafael

 

-----Original Message-----
From: users [mailto:[hidden email]] On Behalf Of [hidden email]
Sent: Thursday, June 07, 2018 2:32 PM
To: Users mailing list for Scilab <[hidden email]>
Subject: Re: [Scilab-users] circshift() : Scilab Enhancement Proposal

 

>Samuel,

> 

>The idea and the implementation of the end-points interpolation is that

>this is done on the input data (big slope), not on the FFT output.

 

This is clear

 

>Maybe be it needs some further work. Tbc.

 

I don't think so.

 

>Noting also that between the endpoints of the DFT periodic input, there is the interval of one sample.

 

That is to say: Let u(1:$) be the original signal.

Since it is virtually periodic, the FFT sees u($+1)=u(1).

Do we agree about this?

 

Then: Do we agree on that the |slope| across the shifted edges of u is necessarily greater or equal to |u($)-u(1)|/1 ?

 


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

Hello Rafael,

Le 07/06/2018 à 15:04, Rafael Guerra a écrit :

Hi Samuel,

 

Fyi, many DFT references recommend averaging the values at endpoints and discontinuities in general. See for instance:

 

Briggs, W. L. and V. E. Henson [1005] The DFT: an owner's manual for the Discrete Fourier Transform, SIAM, Philadelphia.


>and discontinuities in general

Yes, that's a point. If a specific processing is used for the edges, it would look strange to not implement it as well in the body of the initial signal. From here, a criteria (and likely some threshold) must be set to decide what's a discontinuity, and what's not.
I did not go into any reading -- and frankly, if there is a summarized performances comparison and a standard published procedure --, it would be easier just to implement it, instead of reinventing the wheel with external tests. Then, i am afraid that it will come either with some choices with respect to the type of input signal, or with a bunch of processing options (making circshift a signal processing function rather than just a general matrix handling operation).

Anyway, no damping window could process inner discontinuities.

To me, the main advantage of the DFT was to avoid local interpolations, in order to stay simple.
If the algo then implements some interpolations, why not performing the fractional part of the shift
only by interpolation, instead of in addition to the DFT?
If you can provide some quantified rationale and possibly some finalized algo, it would be fine.

Best regards
Samuel


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users
Rafael Guerra Rafael Guerra
Reply | Threaded
Open this post in threaded view
|

Re: circshift() : Scilab Enhancement Proposal

Hi Samuel,

 

There might be an advantage of using the suggested DFT approach for fractional circular shifting of continuous/bandlimited input signals. This is a restrictive but quite useful class of signals.

 

For the more general case of input series, other interpolation schemes should perform better.

 

PS:

I could not find a good reference on this topic so far.

 

Regards,

Rafael

 

From: users [mailto:[hidden email]] On Behalf Of Samuel Gougeon
Sent: Sunday, June 17, 2018 8:19 PM
To: Users mailing list for Scilab <[hidden email]>
Subject: Re: [Scilab-users] circshift() : Scilab Enhancement Proposal

 

Hello Rafael,

Le 07/06/2018 à 15:04, Rafael Guerra a écrit :

Hi Samuel,

 

Fyi, many DFT references recommend averaging the values at endpoints and discontinuities in general. See for instance:

 

Briggs, W. L. and V. E. Henson [1005] The DFT: an owner's manual for the Discrete Fourier Transform, SIAM, Philadelphia.


>and discontinuities in general

Yes, that's a point. If a specific processing is used for the edges, it would look strange to not implement it as well in the body of the initial signal. From here, a criteria (and likely some threshold) must be set to decide what's a discontinuity, and what's not.
I did not go into any reading -- and frankly, if there is a summarized performances comparison and a standard published procedure --, it would be easier just to implement it, instead of reinventing the wheel with external tests. Then, i am afraid that it will come either with some choices with respect to the type of input signal, or with a bunch of processing options (making circshift a signal processing function rather than just a general matrix handling operation).

Anyway, no damping window could process inner discontinuities.

To me, the main advantage of the DFT was to avoid local interpolations, in order to stay simple.
If the algo then implements some interpolations, why not performing the fractional part of the shift
only by interpolation, instead of in addition to the DFT?
If you can provide some quantified rationale and possibly some finalized algo, it would be fine.

Best regards
Samuel


_______________________________________________
users mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users