Минимальное количество D-триггеров

Я столкнулся со следующим вопросом и не могу быть уверен в ответе. Есть ли у вас какие-либо предложения, любая помощь будет высоко оценена.

Последовательность Фибоначчи F(n) определяется как F(1)=1, F(2)=1 и Fn=F(n-2) + F(n-1) для всех целых чисел n>= 3. Что такое минимальное количество D-триггеров, необходимое (вместе с комбинационной логикой) для разработки схемы счетчика, которая выводит первые семь чисел Фибоначчи (т. е. от F1 до F7), а затем выполняет цикл?

(A) 3 (B) 4 (C) 5 (D) 6 (E) 7

заранее спасибо


computer-science flip-flop computer-architecture
person serkank    schedule 09.11.2011    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Минимальное количество требуемых триггеров будет всего 3 для получения семи различных выходов. Но тогда это включает в себя множество комбинаторных схем для декодирования семи уникальных выходов в требуемую последовательность Фибоначчи. Одна из этих схем декодирования использует четыре мультиплексора 4: 1, где каждый выход мультиплексора представляет один бит последовательности Фибоначчи.

Но используя 4 триггера, мы можем получить синхронный счетчик, который проходит только эти состояния 1,1,2,3,5,8,13 и циклически. Я думаю, что этот процесс включает в себя немного меньше схемы. Здесь следует позаботиться только о том, чтобы дифференцировать появление 1 дважды, что можно сделать с помощью дополнительного вентиля nand.

person Reddy    schedule 28.06.2013

arrow_upward
0
arrow_downward

Во-первых, вам нужно уметь считать до 7. Вот тут-то и пригодятся шлепанцы, потому что у них есть память, которая вам нужна, чтобы запомнить счет. Простым подходом было бы создание кольцевого буфера, но, поскольку вам разрешена бесконечная комбинаторная логика, вы можете улучшить это, создав двоичный счетчик.

Теперь, когда у вас есть схема, которая обеспечивает 7 уникальных выходов, вы можете дополнить ее дополнительной комбинаторной логикой, чтобы декодировать эти выходы в 7 значений по вашему выбору.

person Neil    schedule 09.11.2011
comment
Понятно, я не подумал об использовании комбинаторной логики. Тогда мне действительно нужно 7 шлепанцев? Разве я не могу просто представить их как 000, 001, ...., 110. Может быть, это уменьшит число до 3? - person serkank; 10.11.2011
comment
@serkank Действительно, я считаю, что вы должны иметь возможность настроить 3 триггера на счет до 7. - person Neil; 11.11.2011

arrow_upward
0
arrow_downward

Вы можете использовать регистр сдвига с линейной обратной связью:

-- .--------/---------------------.
-- |        4             +----+  |
-- |          .-----------| __ |  |
-- |          |           | \  |--*-/-- F(n)
-- |  +--+    |  +--+     | /_ |    4
-- '--|  |--/-*--|  |--/--|    |
--    |> |  4    |> |  3  +----+
--    +--+       +--+
--   F(n-1)     F(n-2)

Всего вам нужно 7 флопов (4+3).

Поскольку ваш диапазон невелик, самые большие числа, которые вы добавите, — это 8 и 5, чтобы получить F (7) = 13.

Реальный дизайн также будет регистрировать выход F (n) (по причинам времени).

Самому считать до 7 не нужно - эта система может работать в свободном режиме и с увеличенной шириной сцены считать сколько угодно. Ему потребуется значение триггера для сброса, если вам нужна последовательность фиксированной длины.

person user1070420    schedule 05.12.2011