Вдохновленный недавней популярностью nandgame на TNB и моей собственной предыдущей задачей .
Фон
Плотно упакованный десятичный код (DPD) - это способ эффективного хранения десятичных цифр в двоичном виде. Он хранит три десятичных знака (от 000 до 999) в 10 битах, что намного эффективнее, чем наивный BCD (который хранит одну цифру в 4 битах).
Таблица перевода
DPD предназначен для простого преобразования между битами и цифрами путем простого сопоставления с шаблоном сверху вниз. Каждый битовый набор определяет, сколько старших цифр (8-9) имеет число, где они находятся и как перемещать биты, чтобы сформировать десятичное представление.
Ниже приведена таблица преобразования из 10 битов DPD в три десятичных знака. Каждая десятичная цифра представлена в виде 4-битного двоичного кода (BCD). Обе стороны пишутся слева направо от самой значимой цифры к наименьшей.
Bits => Decimal (Digit range)
a b c d e f 0 g h i => 0abc 0def 0ghi (0-7) (0-7) (0-7)
a b c d e f 1 0 0 i => 0abc 0def 100i (0–7) (0–7) (8–9)
a b c g h f 1 0 1 i => 0abc 100f 0ghi (0–7) (8–9) (0–7)
g h c d e f 1 1 0 i => 100c 0def 0ghi (8–9) (0–7) (0–7)
g h c 0 0 f 1 1 1 i => 100c 100f 0ghi (8–9) (8–9) (0–7)
d e c 0 1 f 1 1 1 i => 100c 0def 100i (8–9) (0–7) (8–9)
a b c 1 0 f 1 1 1 i => 0abc 100f 100i (0–7) (8–9) (8–9)
x x c 1 1 f 1 1 1 i => 100c 100f 100i (8–9) (8–9) (8–9)
нотации
- Буквы
a
в нижнем регистреi
- это биты, которые копируются в десятичное представление. 0
и1
являются точными битами во входных или выходных битовых комбинациях.x
биты игнорируются при преобразовании.
задача
Создайте логическую схему с использованием двух входных вентилей NAND для преобразования 10 битов DPD в 12 битов BCD.
Примеры
Подчеркнутые биты являются битами сопоставления с образцом.
DPD Decimal BCD
0 0 0 0 0 0 0 1 0 1 005 0000 0000 0101
^
0 0 0 1 1 0 0 0 1 1 063 0000 0110 0011
^
0 0 0 1 1 1 1 0 0 1 079 0000 0111 1001
^ ^ ^
0 0 0 0 0 1 1 0 1 0 090 0000 1001 0000
^ ^ ^
0 0 0 1 0 1 1 1 1 0 098 0000 1001 1000
^ ^ ^ ^ ^
1 0 1 0 1 1 1 0 1 0 592 0101 1001 0010
^ ^ ^
0 0 1 1 0 0 1 1 0 1 941 1001 0100 0001
^ ^ ^
1 1 0 0 1 1 1 1 1 1 879 1000 0111 1001
^ ^ ^ ^ ^
1 1 1 0 0 0 1 1 1 0 986 1001 1000 0110
^ ^ ^ ^ ^
0 0 1 1 1 1 1 1 1 1 999 1001 1001 1001
^ ^ ^ ^ ^
1 1 1 1 1 1 1 1 1 1 999 1001 1001 1001
^ ^ ^ ^ ^
Критерий оценки и выигрыша
Счет - это количество входов NAND с двумя входами, используемых в вашей схеме. Самый низкий балл побеждает.
Вы можете определить небольшие компоненты в терминах вентилей NAND с двумя входами, а затем использовать их в своей окончательной конструкции. Если компонент X
включает в себя N
входные вентили NAND, каждое использование X
добавляет N
к вашему счету. Для базовых логических элементов это означает:
- НЕ: +1
- 2-входное И: +2
- 2-х входное ИЛИ: +3
- 2 входа XOR: +4
источник
a
вi
виду и процесс преобразования. Пройдите шаги, вместо того, чтобы просто показывать примеры и надеяться, что мы поняли из этого.Ответы:
45 NAND (или 43)
45 кажется абсолютным минимумом, но можно достичь 43 NAND с помощью хитрости: если предположить, что самые большие числа правильно закодированы.
888, 889, 898, 899, 988, 989, 998, 999 должны быть закодированы с 2-мя старшими битами как 00, требуя только 43 NAND для декодирования.
Однако в спецификации для декодирования они указаны как игнорируемые, то есть они могут быть чем угодно. Разумно предположить, что эта более свободная спецификация может потребовать еще меньше ворот, но верно и обратное. Для этого нужно 45 ворот. Эта экономия может дать реальные преимущества для реальных цепей.
Я также обнаружил схемы, которые были значительно более эффективными и быстрыми и содержали еще несколько ворот.
На этот раз не нарисованное карандашом изображение схемы. Возможно позже.
Схема представлена в явном коде Verilog, готовом к работе с включенным тестом.
Verilog код:
источник
65 62 6058 NANDSПринимая входы как
i0
дляi9
и выходы , какo0
кo9, oa, ob
намТестовые рамки Python для проверки правильности построения.
источник