Aligning ones to LSBs

[shaiko]

Hi,

I'm looking for an algebraic solution to align the '1' bits of a vector to the LSB's.
For example:

11001001 will transform to: 00001111
1000 will transform to: 0001
1100 will transform to 0011.

I wrote a custom HDL function that achieves the goal but it's quite complex and will probably have poor timing performance.

 

[FlyingDutch]

Hello,

you haven't got full Boolean function table nor written HDL function. Problem you described is such ambiguous that one have difficulty to understand it.

Best regards

 

[wwfeldman]

i do not think you can use algebra to convert and (arbitrary) n bit number
to another (arbitrary?) n bit number with all the 1's put in a row together

if i understand what you wrote,
1000, 0100, 0010 and 0001 all convert to 0001, etc.
this loses all significance of the number (vector)
the original number is unrecoverable

the only way is can think of to do what you suggest is to step through the number, bit by bit
write a 1 when a bit is a 1
after all n bits, pad on the left with zeros to get n bits.

 

[FvM]

You can write either combinational or clocked sequential code to perform the operation. You can write the behavioral description and your synthesis tool will compile it.

Unlike for some other problems, e.g. leading one detector, (see https://www.edaboard.com/threads/solutions-for-leading-one-detector.201958/) there's probably no specific "algebraic" solution for the problem.

 

[shaiko]

there's probably no specific "algebraic" solution for the problem.

(After searching...)Actually there is. but it does require to be able to count the number of ones (which means another custom function).

    function align_ones_lsb
    (
        data : std_logic_vector
    )
    return std_logic_vector is
    variable aligned_ones   : std_logic_vector ( data ' range )                         ;
    variable shifted_one    : unsigned ( data ' range )         := ( others => '0' )    ;
    variable number_of_ones : natural                                                   ;
    begin
        number_of_ones := count_ones ( data ) ;
        for index in data ' range
        loop
            if index = number_of_ones then
                shifted_one ( index ) := '1' ;
            end if ;
        end loop ;

        aligned_ones := std_logic_vector ( shifted_one - to_unsigned ( 1 , data ' length ) ) ;
        return aligned_ones ;
    end function ;

 

[FvM]

I don't recognize an useful algebraic approach. The "aligned_ones" vector can be generated easily in the loop, there's no advantage of using a substraction.

 

[shaiko]

I don't recognize an useful algebraic approach. The "aligned_ones" vector can be generated easily in the loop, there's no advantage of using a substraction.

Can you post how you'd calculate it with a loop ?

 

[dpaul]

AS I see it, the requirement is to count the number of 1s in a std_logic_vector and push all the accumulated 1s to the slv's LSB without alterting the slv dimension.
Must it be an algebraic solution?

In hw design you just apply the most elegant solution that needs the min amount of silicon real-estate.

 

[FvM]

Something like

j:=0;
for i in data'range loop
  if data(i) = '1' then
    aligned_ones(j):='1';
    j:=j+1;
  end_if;
end loop ;

--- Updated Jan 12, 2021 ---

In hw design you just apply the most elegant solution that needs the min amount of silicon real-estate.

Basically agreed. In addition readability of the code.

A correct behavioral description compiled by a good synthesis tool often results in an acceptable result, at least for a combinational design which maps to a logic optimization problem.

FPGA design involves an additional dimension of mapping the logic to pre-structured hardware like logic array blocks with dedicated carry chains. The above link shows that a problem isn't necessarily optimally solved by the tools.