[dimn 0]

Приветствую!

 

Подскажите как сделать более элегантно подсчет кол-ва единичных битов (от 0го бита до старшего)? Счет должен останавливаться до первого нуля.

 

Например:

1)

data = 8'b01011111

кол-во: 5

 

2)

data=8'b00001011

кол-во: 2

 

мой вариант:

assign sum =    (data[0]) ? a    : 4'd0;
assign a =        (data[1]) ? b    : 4'd1;
assign b =        (data[2]) ? c    : 4'd2;
assign c =        (data[3]) ? d    : 4'd3;
assign d =        (data[4]) ? e    : 4'd4;
assign e =        (data[5]) ? f    : 4'd5;
assign f =        (data[6]) ? g    : 4'd6;
assign g =        (data[7]) ? h    : 4'd7;
assign h =        (data[8]) ? 4'd8    : 4'd7;

 

-Dima

[Artem_Petrik 0]

че-то типа этого:

reg [3:0] sum;
integer i;
always @(*)
  begin
    sum = 0;
    for(i=0;i<8;i=i+1) sum = sum + data[i];
  end

[Джеймс 3]

че-то типа этого:

 

У автора вопроса несколько более сложное условие.

[Artem_Petrik 0]

У автора вопроса несколько более сложное условие.

 

Действительно, недосмотрел :unsure: . 

 

reg [3:0] sum;
integer i;
always @(*)
  begin
      sum = 0;
      for(i=0;(i<8 && data[i]==1'b1);i=i+1) sum = sum + data[i];
  end

[Andron_ 0]

если данные строго 8-ми битные, можно табличку на 256 ячеек изобразить.

[Джеймс 3]

reg [3:0] sum;
integer i;
always @(*)
  begin
      sum = 0;
      for(i=0;(i<8 && data[i]==1'b1);i=i+1) sum = sum + data[i];
  end

 

Мне просто интересно - вы пробовали когда-нибудь синтезировать этот код, или тот, что был в Вашем предыдущем сообщении? Или Вы рассматриваете эти примеры лишь исключительно в приложении к симуляции?

Мне некоторое время назад не удалось заставить Synplify "понять" код, практически повторяющий Ваш первый. После просмотра результатов (RTL viewer) всё время оказывалось, что логика искорежена синтезатором (уже не помню, что именно).

А Ваш новый код синтезироваться вообще не будет. FOR лишь помогает размножить примитивы, но не может "принимать решения" в процессе работы.

[Leka 0]

Обычный приоритетный энкодер - ищем самый младший "0".

[Artem_Petrik 0]

Мне просто интересно - вы пробовали когда-нибудь синтезировать этот код, или тот, что был в Вашем предыдущем сообщении? Или Вы рассматриваете эти примеры лишь исключительно в приложении к симуляции?

Мне некоторое время назад не удалось заставить Synplify "понять" код, практически повторяющий Ваш первый. После просмотра результатов (RTL viewer) всё время оказывалось, что логика искорежена синтезатором (уже не помню, что именно).

А Ваш новый код синтезироваться вообще не будет. FOR лишь помогает размножить примитивы, но не может "принимать решения" в процессе работы.

Ну, первый пример синтезируется квартусом без проблем.Правда дает не самую оптимальную логику, но, думаю, при длине входного вектора всего 8 бит, результат будет слабо отличатся от оптимального. Такой код уже обсуждался, например в http://electronix.ru/forum/index.php?showt...=62749&st=0

 

Что касается второго примера, то возможно Вы правы, сейчас нет возможности проверить. Однако решить задачу именно подобным образом все же можно, правда после того, как Leka указал, что задача суть

Обычный приоритетный энкодер - ищем самый младший "0".

мои извращения с циклом for уже мне самому не нравятся. Действительно надо делать приоритетный энкодер при помощи casex.

[SergeyF 0]

мои извращения с циклом for уже мне самому не нравятся. Действительно надо делать приоритетный энкодер при помощи casex.

Это не извращения! Как Вы сделаете приоритетный шифратор для 64-х разрядного чиcла, например? Пальцы ведь заболят. Не знаю как Synplify, а Quartus вот такое кушает:

 

wire [WIDTH:0] dext;
assign dext = {1'b0,data};
always @(*)
begin
sum = 0;
while (dext[sum]==1'b1 && sum<WIDTH) sum=sum+1;
end

 

и в результате занимает меньше места и меньше слоев логики, чем если описать casex, if или assign. Проверено в своих проектах.

[Egel 0]

Это все относительно. Если нужно быстро написать - то так сойдет, но в реале это даст огромное кол-во сумматоров (любой высокоуровневый алгоритм такого типа для данной задачи). Самое менее затратное по ресурсам - дерево сумматоров или дерево Уоллеса. Я сталкивался с этой задачей. Но и так и так синтезироваться конечно будет.

 

С уважением

[Shtirlits 0]

Похожие схемы synplify плохо обрабатывает, от него, как мне кажется, только торговая марка осталась.

XST и Quartus предпочтительнее и удобнее.

 

Мне нравится как написано: наглядно, кратко и ясно, нагрузка на мозг читающего/проверяющего небольшая, на дополнительную информацию, например, на "дерева Уоллеса", не ссылается. Читателю нужно знать лишь спецификацию и язык, но не архитектуру железа.

 

Все хорошо, если входной вектор укладывается в размер LUT-ов или ROM-ов.

Для больших длин я бы попытался применить carry chain, если есть.

Если не будет успевать - применить прием, как в look ahead adder, то есть, поделить вектор на несколько частей, скажем, на две или сколько влезет в LUT. Считать по частям отдельно длины подряд идущих единиц. Потом объединять результат.

http://en.wikipedia.org/wiki/Carry_look-ahead_adder

Главное, не сделать ошибки при реализации аппаратно-ориентированной версии.

 

PS: Что такое "дерево Уоллеса" ?

[SergeyF 0]

Это все относительно. Если нужно быстро написать - то так сойдет, но в реале это даст огромное кол-во сумматоров (любой высокоуровневый алгоритм такого типа для данной задачи). Самое менее затратное по ресурсам - дерево сумматоров или дерево Уоллеса. Я сталкивался с этой задачей. Но и так и так синтезироваться конечно будет.

Сумматоров?

 

Вот результаты Quartus для Cyclone II:

8 бит - 10лэ, 2 слоя

16 бит - 24лэ, 4 слоя

32 бит - 48лэ, 10 слоев

64 бит - 97лэ, 18 слоев

И даже на уровне RTL в QII ни одного сумматора. Ни одной цепи переноса не задействовано.

 

Попробуйте построить дерево сумматоров в базисе ПЛИС, хоть пирамидальное, хоть Уоллеса, менее затратное по ресурсам. Если какой-то синтезатор плохо работает - это не повод отказываться от высокоуровневого описания. Меня больше беспокоит, что реализация 32 и 64 бит откровенно медленная и ее нужно факторизовать и действительно строить по другому, пусть ценой роста количества ресурсов.

 

P.S. Wallace tree - схема сложения с сохранением переносов. Мы строим не пирамиду из сумматоров, например, при сложении частичных произведений в умножителях, а складываем биты в одном столбце для нескольких частичных произведений. Вот пример.

 

P.P.S. Кстати, спасибо за идею о проверке эффективности. Разложил 64-битную схему на 4 16-ти битных модуля. В результате - 91лэ, 7 слоев. логики. Но все равно ни одного сумматора. Попробую еще поиграть.

Изменено 1 ноября, 2009 пользователем Sergey'F

[SKov 0]

P.P.S. Кстати, спасибо за идею о проверке эффективности. Разложил 64-битную схему на 4 16-ти битных модуля. В результате - 91лэ, 7 слоев. логики. Но все равно ни одного сумматора. Попробую еще поиграть.

Просто в квартусе оптимизатор неплохой. Вот и нет сумматоров ;)

Задача стандартная. Если хотите быструю схему (с малой глубиной логики) - пишите case, если хотите немножко сократить число элементов за счет некоторого увеличения глубины логики - пишите предварительные проверки. Например, можно проверить первую половину данных на все единицы и после этого работать только с половиной данных. Можно дальше выполнять проверку половины от этой половины и т.д. Если продолжить этот процесс, то глубина пирамиды получится логарифмической, а сложность по элементам минимальной. Все остальные варианты лежат между этими двумя крайними точками (case и пирамидой). А все, что не лежит там - то от лукавого ;)

[khlenar 5]

Если засинхронизировать то один из вариантов:

module countbit(
        input clk,             //такт...
        input [7:0] data,      //данные
        input load,            //загрузка данных
        output reg fin,        //флаг, счет закончен
        output reg [4:0] count //результат
        );
        
    bit [7:0] tempbuff;
        
    always @ (posedge clk or posedge load) begin     
      if(load) begin
        tempbuff <= data;
        fin <= 0;
        count <= 0;
      end
     else begin
        if(tempbuff[0]) begin
          tempbuff <= tempbuff >> 1;
          count++;
        end
      else fin <= 1;    
     end 
   end
endmodule        

module test;
  bit clk;
  bit [7:0] data;
  bit load;
  bit fin;
  bit [4:0] count;

    initial begin
     clk = 0;
     data = 0;
     load = 0;

    #5 data = 8'b11001111;
    #5 load = 1;
    #2 load = 0;
    wait(fin == 1); //Ждать пока счет не закончен
    
    #5 data = 8'b10101011;
    #5 load =1;
    #2 load = 0;
    wait(fin == 1); //Ждать пока счет не закончен
    #5 $stop;
    end
    
    always #2 clk = ~clk;
    
countbit P1 (
   .clk(clk),
   .data(data),
   .load(load),
   .fin(fin),
   .count(count)
  );
endmodule

проверил в ModelSim, управляюшие сигналы можно по разному сделать, как требует это "железо".

[des00 25]

P.P.S. Кстати, спасибо за идею о проверке эффективности. Разложил 64-битную схему на 4 16-ти битных модуля. В результате - 91лэ, 7 слоев. логики. Но все равно ни одного сумматора. Попробую еще поиграть.

 

сравните свои результаты с результатами полученными здесь %) http://electronix.ru/forum/index.php?showt...mp;#entry549588

 

ЗЫ. уже обсуждали оптимальную структуру выполняющую подобную функцию %)