реклама на сайте
подробности
 
 Wiki Wiki  Photo Photo  Forum Forum  Reviews Reviews  Help (!) Help (!)
 
> Подсчет числа одинаковых разрядов двоичного числа, ищется комбинаторная реализация
glock17
сообщение Apr 28 2006, 06:41
Сообщение #1


Частый гость
**

Группа: Свой
Сообщений: 163
Регистрация: 3-09-04
Пользователь №: 586
help.gif
Задача следующая:

имеется 32-х разрядное число. Нужно вычислить, сколько у этого числа последовательных нулей или единиц, начиная со старшего разряда. Поясню на примере 8-разрядного числа:

0001xxxx или 1110xxxx дают результат 2 (3 одинаковых соседних бита в старших разрядах)
10xxxxxx или 01xxxxxx дают результат 0 (одинаковых соседних битов нет)
0000001x или 1111110x дают результат 5 (6 одинаковых соседних битов в старших разрядах)

x означает, что значение этих битов уже не имеет значения.

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

Буду благодарен за любые конструктивные идеи. cheers.gif
Go to the top of the page
 
+Quote Post
 
 Start new topic
Ответов
Postoroniy_V
сообщение Apr 28 2006, 07:28
Сообщение #2


МедвеД Инженер I
****

Группа: Свой
Сообщений: 816
Регистрация: 21-10-04
Пользователь №: 951
Цитата(glock17 @ Apr 28 2006, 10:41) *
help.gif
Задача следующая:

имеется 32-х разрядное число. Нужно вычислить, сколько у этого числа последовательных нулей или единиц, начиная со старшего разряда. Поясню на примере 8-разрядного числа:

0001xxxx или 1110xxxx дают результат 2 (3 одинаковых соседних бита в старших разрядах)
10xxxxxx или 01xxxxxx дают результат 0 (одинаковых соседних битов нет)
0000001x или 1111110x дают результат 5 (6 одинаковых соседних битов в старших разрядах)

x означает, что значение этих битов уже не имеет значения.

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

Буду благодарен за любые конструктивные идеи. cheers.gif

если всё упирается в быстродействие, тогда делаете таблично(ROM)
адрес это ваши 0001xxxx и т.д.
а на выходе уже получаете "ответ" за 1 такт

а комбинационой логикой врядли получится быстрее


--------------------
Cogito ergo sum
Go to the top of the page
 
+Quote Post
glock17
сообщение Apr 28 2006, 08:10
Сообщение #3


Частый гость
**

Группа: Свой
Сообщений: 163
Регистрация: 3-09-04
Пользователь №: 586
Цитата
если всё упирается в быстродействие, тогда делаете таблично(ROM)
адрес это ваши 0001xxxx и т.д.
а на выходе уже получаете "ответ" за 1 такт

а комбинационой логикой врядли получится быстрее


Думал уже... Это какой же ROM нужен, чтобы таким макаром 32-х битное число обработать... sad.gif
Проблема в том, что эта процедура - мизерная часть офигенно развесистого алгоритма, который пишется для создания ASIC на его базе, поэтому затраты по площади (так же, как и быстродействие) - основные проблемы.
Я уже попробовал минимизировать аналогичную функцию для 8-битного числа - результат впечатляет biggrin.gif
С 32-битным даже пробовать не буду.
Похоже, вариантов всего два - попытаться вообще исключить эту гнусную процедуру из алгоритма или все таки делать ее синхронно.
Go to the top of the page
 
+Quote Post

Сообщений в этой теме
- glock17   Подсчет числа одинаковых разрядов двоичного числа   Apr 28 2006, 06:41
- - sazh   А можно посмотреть на этот код?   Apr 28 2006, 07:15
|- - glock17   ЦитатаА можно посмотреть на этот код? Какой код? ...   Apr 28 2006, 07:55
|- - glock17   Всем откликнувшимся - большое спасибо! Проблем...   May 1 2006, 00:58
- - lelik   Если данные идут последовательно, то можно использ...   Apr 28 2006, 08:14
- - des00   Цитата(glock17 @ Apr 28 2006, 01:41) За...   Apr 28 2006, 08:26
- - RobFPGA   Приветствую! У меня вот этот вариант работает...   Apr 28 2006, 09:10
- - sazh   module comp32 ( input [31:0] in, output [4:0] out...   Apr 28 2006, 09:33
- - Gate   glock17, любые верилоговские конструкции, не стоящ...   Apr 28 2006, 09:34
- - sazh   To Gate В вашем примере неправильно будет интерпит...   Apr 28 2006, 10:01
|- - Gate   Цитата(sazh @ Apr 28 2006, 14:01) To Gate...   Apr 28 2006, 10:37
|- - id_gene   Цитата(sazh @ Apr 28 2006, 14:01) To Gate...   Apr 29 2006, 10:08
- - Magnum   To Gate: Это последовательный путь.. А надо паралл...   Apr 28 2006, 10:08
- - sazh   Причем тут последовательный или параллельный. И то...   Apr 28 2006, 10:20
- - sazh   Уважаемый id_gene. Дело в том, что я не программис...   Apr 29 2006, 19:31
|- - DS_   По моему делается из 31 элемента XOR, который свод...   Apr 29 2006, 20:27
- - Chudik   Я тоже, почитав ответы, пришёл к выводу об использ...   Apr 30 2006, 18:02
|- - Gate   Цитата(Chudik @ Apr 30 2006, 22:02) Я тож...   Apr 30 2006, 18:24
- - DS_   А как Вы думаете, что построится по Вашим IF ? Это...   Apr 30 2006, 18:24
- - Chudik   Цитата(DS_ @ Apr 30 2006, 11:24) А как Вы...   May 1 2006, 01:10
- - sazh   А разве мой первый вариант это разве не XOR в связ...   May 2 2006, 06:48

 

Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

RSS Текстовая версия Сейчас: 20th July 2025 - 22:28
Рейтинг@Mail.ru


Страница сгенерированна за 0.01389 секунд с 7
ELECTRONIX ©2004-2016