Микроконтролери и електроника
http://mcu-bg.com/mcu_site/

Задача за интервю
http://mcu-bg.com/mcu_site/viewtopic.php?f=7&t=6441		 Страница 1 от 1
Автор:  HCL [ Пет Яну 09, 2009 3:29 pm ]
Заглавие:  Задача за интервю
Новата задача тип Интервю на "Adventures in ASIC Digital Design"
http://asicdigitaldesign.wordpress.com/

"Design a circuit with minimum logic that receives a single digit, coded BCD (4 wires) and as an output gives you the result multiplied by 5 - also BCD coded (8 wires)."

Предложете схемно решение с минимално количество логика на следния проблем. На входа получавате единична BCD кодирана цифра (4 bits), която следва да бьде умножена по 5 и предадена на изхода в BCD формат (8 bits).
Пример:
input=5 (0101) => output=25 (0010 0101)

Сьветвам ви, преди да погледнете решенията на страницата, да опитате сами. Сред предложените отговори има особенно интересен подход.
Автор:  zaphod [ Пет Яну 09, 2009 3:42 pm ]
Заглавие: 
старшите три бита стават на десетици а младшия бит се цепва на две и отива на бит 0 и бит 2. нула елемента логика :)
Автор:  HCL [ Пет Яну 09, 2009 4:27 pm ]
Заглавие: 
Така е, но по кой метод стигна до извода?
Разпозна визуално структурата в таблицата или използва друг подход.
Сред предложените решения има едно особено интересно

Цитат:
5*(8a3+4a2+2a1+a0) = 40a3+20a2+10a1+5a0 = 40a3+20a2+10a1+4a0+a0

maps to

80b7+40b6+20b5+10b4 + 8b3+4b2+2b1+b0

if b6==a3, b5==a2, b4==a1, b2==a0 and b0=a0
Автор:  zaphod [ Пет Яну 09, 2009 4:46 pm ]
Заглавие: 
ами по кой метод, за такива неща метод няма. първо се пробвах конвенционално, със едно шифтване и сумиране и няква десетична корекция, после видях че няма да стане и викам я да видим в десетична система директно.
Автор:  bateAz [ Пет Яну 09, 2009 5:09 pm ]
Заглавие: 
Умноженията по число, което е основа или степен на основата на бройната система, не изисква логически схеми. В случая на BCD основата е 10, а не 2, така че на 5 се умножава без логика.
Автор:  HCL [ Пет Яну 09, 2009 7:02 pm ]
Заглавие: 
Получи се наистина интересно :)
@Zaphod като "софтуерист" търси подходяш алгоритъм за решението на проблема, чрез сумиране и десетична корекция.
Аз изобразих функцията таблично за да разпозная pattern-а ако има такьв, ако не щях да я развия директно с помощта на Karnaugh map или по Quine-McCluskey.
@bateAz използва формален подход, характерно за един системен архитект.
Още идеи?

Всяка една от споменатите техники е в състояние да ни отведе до оптимално или близко до оптималното решение.
Всеки един от нас е трьгнал по различен път, макар и да е способен да разпознае останалите щом ги види.
Хареса ми идеяата на автора. Независимо от това, с какво знание/инструменти разполагаме понякога е трудно да надскочим ограниченията, които сами си налагаме. Добре е когато човек разширява крьгозора си. Hе само в личен план, но и в професионален. За нас като инженери и програмисти е особено важно да умеем да подхождаме по различен начин кьм проблемите с които се борим. Това като малко лирично отклонение.

Цитат:
IMHO there is nothing really clever or sophisticated about this problem, but it demonstrates beautifully how it is sometimes hard for us to escape our initial ideas and approaches about a problem.
Автор:  ДедоБоре [ Пет Яну 09, 2009 7:19 pm ]
Заглавие: 
HCL написа:
Добре е когато човек разширява крьгозора си.

не е добре. много е добре 8)
Автор:  ps66 [ Пет Яну 09, 2009 7:23 pm ]
Заглавие: 
x*5 == (x*10) / 2

0 0 0 0 b3 b2 b1 b0 * 5 == (b3 b2 b1 b0 0 0 0 0)/2 == 0 b3 b2 b1 0 b0 0 b0
(при деление на 2 на десетиците остатъка е 0 или 5 според b0 ... затова е 0 b0 0 b0)
Автор:  ToHu [ Пет Яну 09, 2009 8:21 pm ]
Заглавие: 
Ами както батето каза няма нужда от логика, бит нула и две от единиците на резултата се мапват към бит 0 на входа, и съответно бит 0 = бит 1, бит 1 = бит 2, бит 3 = бит 4, бит 5= 0 за резултата, съответно свързан към входа.
Автор:  zaphod [ Пет Яну 09, 2009 8:39 pm ]
Заглавие: 
сега да пусна заядливостта си в действие :)
Цитат:
Умноженията по число, което е основа или степен на основата на бройната система, не изисква логически схеми. В случая на BCD основата е 10, а не 2, така че на 5 се умножава без логика.

всичко това е много благородно (чии лаф е това?), но 5 не е степен на десятката. степените на десятката са 0.01, 0.1,1,10,100.. между тях не виждам 5.
и за да не каже някой "е се тая, степен или кратно", то да отбележа че същата задача приложена не към двоично десетичен код, а към троично десетичен, няма да може да се реши по тоя хитър начин.
Автор:  ps66 [ Пет Яну 09, 2009 9:22 pm ]
Заглавие: 
zaphod написа:
... то да отбележа че същата задача приложена не към двоично десетичен код, а към троично десетичен, няма да може да се реши по тоя хитър начин.


обаче за всяка бройна система с база B (ЧЕТНО), решението е подобно (ако е умножава по B/2) !
Автор:  tgi [ Съб Яну 10, 2009 4:15 am ]
Заглавие: 
Пет наистина не е степен на 10, и бит 0 не може да се "цепне" на две....
Май не видях много работещи решения дотук :-).

А е елементарно - старшите 4 бита на резултата са входното число >>1 (*10/2, инак казано горните 3 бита
на входното число - това вече доста го направиха), младшите 4 бита са '5 AND [бит 0 на входното число]'
(т.е. 0 или 5)....

[edit] За по-ясно:

q7=0
q6=i3
q5=i2
q4=i1
*
q3=0
q2=i0
q1=0
q0=i0

Само жици.... никакъв силиций :-).
[/edit]
Автор:  ps66 [ Съб Яну 10, 2009 9:15 am ]
Заглавие: 
tgi написа:
Пет наистина не е степен на 10, и бит 0 не може да се "цепне" на две....
Май не видях много работещи решения дотук :-).

А е елементарно - старшите 4 бита на резултата са входното число >>1 (*10/2, инак казано горните 3 бита
на входното число - това вече доста го направиха), младшите 4 бита са '5 AND [бит 0 на входното число]'
(т.е. 0 или 5)....
...


спИцЯлно (мнооого бавно) за @tgi :

при делението на 2 (повтарям ДВЕ и няма да повтарям :)) на число кратно на 10 ... последната му цифра е 0 или 5
и зависи от това дали е четно/нечетно (разряда на десетицата) ... в нашия случй четността зависи от b0 (по моя пример)

така за младшата цифра остава:
if (b0)
=5
else
=0

или
(b0) ? 5 : 0;

или (класиката)
(b0 *5)

което логично "навява" на (имаме бит b0 по числото 0101):
0 b0 0 b0


по надолу @tgi може и да не чете!

самоцитирам се:
Цитат:
обаче за всяка бройна система с база B (ЧЕТНО), решението е подобно (ако е умножава по B/2) !


за всяка бройна система с база B (ЧЕТНО и НЕ-ПРОСТО) (4, 6, .. 10, ... 16) горната задачa (x*B/2) има подобно решение
(при B=10 е задачата на темата)
и то е:
0 b3 b2 b1 x x x x
където: x x x x , e B/2 като всяка негова 1-ца е заместена с b0 (от побитовато умнoжение b0*B/2 !)

решението е просто, ... защото младшия разряд може да заема само 2 стойности 0 и B/2, което позволява да се избегне каквато и да е логика!

:)
Страница 1 от 1 Часовете са според зоната UTC + 2 часа [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/