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

Full Member level 5
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

Super Moderator
Staff member
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).

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

Super Moderator
Staff member
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.

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:

Points: 2

Replies
3
Views
909
Replies
4
Views
14K
Replies
40
Views
4K
Replies
1
Views
2K
Replies
1
Views
849