Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronic Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Aligning ones to LSBs

shaiko

Advanced Member level 5
Joined
Aug 20, 2011
Messages
2,644
Helped
303
Reputation
608
Reaction score
297
Trophy points
1,363
Activity points
18,300
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

Full Member level 5
Joined
Dec 16, 2017
Messages
301
Helped
39
Reputation
78
Reaction score
38
Trophy points
28
Location
Bydgoszcz - Poland
Activity points
3,098
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

Advanced Member level 3
Joined
Jan 25, 2019
Messages
804
Helped
189
Reputation
378
Reaction score
199
Trophy points
43
Activity points
5,922
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

Super Moderator
Staff member
Joined
Jan 22, 2008
Messages
48,198
Helped
14,202
Reputation
28,663
Reaction score
12,896
Trophy points
1,393
Location
Bochum, Germany
Activity points
279,221
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

Advanced Member level 5
Joined
Aug 20, 2011
Messages
2,644
Helped
303
Reputation
608
Reaction score
297
Trophy points
1,363
Activity points
18,300
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).

Code:
    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

Super Moderator
Staff member
Joined
Jan 22, 2008
Messages
48,198
Helped
14,202
Reputation
28,663
Reaction score
12,896
Trophy points
1,393
Location
Bochum, Germany
Activity points
279,221
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

Advanced Member level 5
Joined
Aug 20, 2011
Messages
2,644
Helped
303
Reputation
608
Reaction score
297
Trophy points
1,363
Activity points
18,300
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

Advanced Member level 4
Joined
Jan 16, 2008
Messages
1,465
Helped
306
Reputation
612
Reaction score
301
Trophy points
1,373
Location
Germany
Activity points
10,973
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

Super Moderator
Staff member
Joined
Jan 22, 2008
Messages
48,198
Helped
14,202
Reputation
28,663
Reaction score
12,896
Trophy points
1,393
Location
Bochum, Germany
Activity points
279,221
Something like
Code:
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 ---

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.
 
Last edited:

    shaiko

    Points: 2
    Helpful Answer Positive Rating

LaTeX Commands Quick-Menu:

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top