XOR on rising edge of two arrays

Hello,

I have two arrays containing 0's & 1's. I want to find xor of the two arrays with two additional conditions:

1. The xor has to be done only in the case of rising edges.
2. To distinguish which array is having rising edge first, I have assigned outputs as 3 levels i.e. 1, 0, -1

Considering an example, if 'a' and 'b' are input arrays and PWM3 is the output array;

a = [0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,0,1]

b = [0,0,0,1,1,1,1,0,0,1,1,1,1,0,1,1,1]

So, the output has be ;

PWM3 = [0,1,1,0,0,0,0,0,1,0,0,0,0,0,-1,-1,0] , so if 'a' has rising edge first output is '1', if 'b' has rising edge first output is '-1', else the output is '0'.

I am trying as given below, but I can't figure out how to take into consideration rising edges only. If someone has any idea about it, please let me know.

Thanks

for p= 1:length(a)
if(a(p)== 1 && b(p)== 0)
PWM3(p) = 1;
elseif (a(p)== 0 && b(p)== 1)
PWM3(p) = -1;
else
PWM3(p) = 0;
end
end

[KALYAN ACHARJYA]

If inputs are a and b

a = [0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,0,1]
b = [0,0,0,1,1,1,1,0,0,1,1,1,1,0,1,1,1]

What would be expected output?

[Mohammad Zulqarnain]

The expected output is: PWM3=[0,1,1,0,0,0,0,0,1,0,0,0,0,0,-1,-1,0]

Answer 1

[Bruno Luong]

a = [0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,0,1];
b = [0,0,0,1,1,1,1,0,0,1,1,1,1,0,1,1,1];

a0 = [0; a(:)];
b0 = [0; b(:)];
i = find(diff(a0) | diff(b0));
js = find(~a0(i) & ~b0(i));
c = a(i)-b(i);
c = c(:);
i(end+1) = 0;
i = [i(js);  i(js+1)];
c = [c(js); -c(js)];
k = i > 0;
PWM3 = cumsum(accumarray(i(k), c(k), [length(a),1])).'

[Jan]

This also replies the answer I expect for the test case:

a = [0,1,1,1,1,1,1,1,0,0,0,1,1,1,0,0,0,0,0,1];
b = [0,0,0,1,1,0,0,1,1,1,0,0,1,1,1,1,0,1,1,1];

In my 2nd approach changes of the phases are identified by the sort index of the joined vectors:

[v, p] = sort([raise, fall]);
m      = strfind(p > numel(raise), [false, true]);

This was inspired by your solution here . After all these years in CSSM and here I still consume your solutions like reading a good book. Thanks.

[Mohammad Zulqarnain]

Thank you for your answer. It works perfectly.

[Bruno Luong]

Jan, same old receipt after all this years. Glad you enjoy the meal as I do. Thanks.

Answer 2

[Jan]

With: https://www.mathworks.com/matlabcentral/fileexchange/41813-runlength

a = [0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,0,1];
b = [0,0,0,1,1,1,1,0,0,1,1,1,1,0,1,1,1];

ab        = a + b;
[v, n, p] = RunLength(ab == 1);
rise      = strfind(ab, [0, 1]) + 1;
v((v == 1) & ~ismember(p, rise)) = 0;
PWM3      = RunLength(v, n) .* sign(a - b)

If runtime is less important or you do not have a C compiler installed, use:

% [EDITED: Function adjusted to reply row vectors]

function [out1, out2, out3] = RunLength(in1, in2)
% RUNLENGTH - RLE coding as M-function
% Author: Jan Simon, Heidelberg, (C) 2013-2020
% $License: BSD (use/copy/change/redistribute on own risk, mention the author) $

if (nargin == 1)               % Encoding: [x] -> [b, n, p] --------------------
   x = in1(:).';
   
   d = [true, diff(x) ~= 0];   % TRUE if values change
   b = x(d);                   % Elements without repetitions
   k = find([d, true]);        % Indices of changes
   n = diff(k);                % Number of repetitions
   
   out1 = b;
   out2 = n;
   out3 = k(1:length(k) - 1);
   
else                           % Decoding: [b, n] -> [x] =======================
   b = in1(:).';               % More convenient names for inputs
   n = in2;
   
   len   = length(n);          % Number of bins
   d     = cumsum(n);          % Cummulated run lengths
   index = zeros(1, d(len));   % Pre-allocate
   index(d(1:len-1)+1) = 1;    % Get the indices where the value changes
   index(1)            = 1;    % First element is treated as "changed" also
   index = cumsum(index);      % Cummulated indices
   
   out1  = b(index);
end
end

[Mohammad Zulqarnain]

Thank you for your answer.

I tried to run the code as you suggested. (I don't have a C compiler, so I used RunLength function given above). But I get an error in the following line:

v((v == 1) & ~ismember(p, rise)) = 0;

The error is:

Error using &

Matrix dimensions must agree.

Error in :

v((v == 1) & ~ismember(p, rise)) = 0;

[Jan]

You can use the debugger by your own to fix the problem.

Either use RunLength_M from the linked submission, or the modified code in my answer, which replies row vectors now.

Answer 3

[Jan]

A second approach:

a    = [0,1,1,1,1,1,1,1,0,0,0,1,1,1,0,0,0,0,0,1];
b    = [0,0,0,1,1,0,0,1,1,1,0,0,1,1,1,1,0,1,1,1];
want = [0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,-1,-1,0]   % correct?

raise  = strfind(or(a,b),  [false, true]) + 1;
fall   = strfind(xor(a,b), [true, false]) + 1;
[v, p] = sort([raise, fall]);
m      = strfind(p > numel(raise), [false, true]);

q           = zeros(size(a));
q(v(m))     = 1;
q(v(m + 1)) = -1;
PWM3        = cumsum(q) .* sign(a - b)

[Mohammad Zulqarnain]

Thank you for your answer.

There is one point which I realized when I ran your code. In some data points, there is +1/-1 output at falling edge. I will try to debug it.

Thank you for your time.

Answer 4

[Walter Roberson]

if state == S_rising_A
    if A(K) == 0
        if B(K) == 0
          state = S_zero   %A was up, has fallen, B is not up, we are all 0
          out(K) = 0
        else
          state = S_rising_B  %A was up but fell, B just rose
          out(K) = -1
        end
    elseif B(K) == 0
        state = S_rising_A  %A is still up, B is still down
        out(K) = 1
    else
        state = S_clearing  %A is up, B just rose, time to clear trailing edge
        out(K) = 0
    end
elseif state == S_rising_B
    if A(K) == 0
        if B(K) == 0
            state = S_zero  %A is not up, B was up but fell, we are all 0
            out(K) = 0
        else
            state = S_rising_B   %A is still down, B is still up
            out(K) = -1
        end
    elseif B(K) == 0
        state = S_rising_A       %A just rose, B was up but just fell
        out(K) = 1
    else
        state = S_clearing  %A just rose, B is up, time to clear trailing edge
        out(K) = 0
    end
elseif state == S_zero
    if A(K) == 0
        if B(K) == 0
            state = S_zero   %both were down and stayed down
            out(K) = 0
        else
            state = S_rising_B %both were down but B rose
            out(K) = -1
        end
    elseif B(K) == 0
        state = S_rising_A  %both were down but A rose
        out(K) = 1
    else
        state = S_clearing  %both were down but both rose, time to clear trailing edge
        out(K) = 0
    end
elseif state == S_clearing
    if A(I) == 0
        if B(K) == 0
            state = S_zero  %clearing trailing edge but both were zero, stop clearing
            out(K) = 0
        else
            state = S_clearing %clearing continuation of trailing edge
            out(K) = 0
        end
    elseif B(K) == 0
        state = S_clearing   %clearing continuation of trailing edge
        out(K) = 0
    else
        state = S_clearing   %clearing continuou of trailing edge
        out(K) = 0
    end
end

.... Actually the above has problems.

I had to decide what to do in a case such as

  1 1 1 1 0 0 0
  0 0 0 0 1 1 1

which I decided should be output 1 1 1 1 -1 -1 -1 -1 -- that is, that the end of the A is considered to be "before" the beginning of the B and so the edge has ended for the first and just started for the second. So that logic is in place.

But at the same time, I had to decide what to do for

  1 1 1 1 0 0 0
  0 1 0 0 1 1 1

I coded the initial part as initial 1 for the A, then because both were 1 that we need to go into clearing mode, so 0 0 0 to clear the rest of the A edge. Then while we are in that clearing mode dealing with the trailing A, we ended A and started B at the same time. For consistency with the above decision that this is two distinct events with no overlap, we should stop clearing and say that we are inside a B edge, for an overall output of [1 0 0 0 -1 -1 -1] -- but the logic I implemented does not keep track of which edge(s) we are removing the trailing part of, so it just thinks "Oh, we haven't seen a clear break yet, so we must still be in clearing mode". That is arguably a bug. There should probably be an S_clearing_A state, an S_clearing_B state, and an S_clearing_both state .

.... I suspect the entire logic could be made a lot shorter by referring to the previous entries in the array. I happen to have a background in Finite State Machines, where you encode what is happening as different states without any explicit lookbacks.

... I bet it could be all coded as regular expressions...

Question for you: if the input starts with a 1, is that to be counted as a rising edge? Is there an implicit 0 before all the inputs? Or is there an implicit "we came in in the middle of something and we won't assume any rising edges until we have seen a definite absense of edges" ?

[Mohammad Zulqarnain]

Thank you for your answer.

The data arrays are such that only one array will change its state at a particular instant. So, the test cases which you have mentioned are not going to occur in the datasets.

As far as starting edge is concerned, we won't assume any rising edges until we have seen a definite absense of edges.

By the way, how to initialize the states. I am trying to initialize as:

state = [];
S_rising_A = [];
S_rising_B = [];
S_zero = [];
S_clearing = [];

But I get an error "Undefined function or variable 'out' ".

Thank you.

[Walter Roberson]

S_* are arbitrary unique scalar values, such as categoricals or enumerations or plain 1, 2, etc. state would be initialized to S_clearing for the case where there is no implied 0.

If only one value can change at a time then the code can be simpler. I will work it out later.