Алло, мы ищем логических дизайнеров! - Playing poohsticks in the Styx — LiveJournal

07:13 pm - Алло, мы ищем логических дизайнеров!

Октябрьская задачка на IBM Ponder This прямо как доктор прописал:

Нужно построить логическую цепь, вычисляющую сумму 12 однобитных значений, использовав минимальное число функций "5 бит -> 2 бита".

Пока рекорд, если верить количеству звездочек в списке решивших задачу, 6 функций (upd: раньше казалось, что 5, но там в одном месте в количестве звездочек была опечатка). ftdf столько может, и я тоже.

А кто сколько может? Кто из программистов может думать в терминах логических цепей?



Пусть 12 входных значений обозначены буквами A-L. Выходы будем обозначать, как это сделал kcmamu в своем решении из 7 функций, буквами U, D, Q, O для разряда единиц, двоек, четверок и восьмерок соответственно, и номером функции. UU, DD, QQ, OO - окончательные результаты.

Первым делом сложим (по модулю 4, с разрядом четверок разберемся позже) две группы по 5 входов:
{D1,U1} = A+B+C+D+E
{D2,U2} = F+G+H+I+J

Теперь как можно быстрее получим окончательное значение разряда единиц (тоже складывая по модулю 4):

{D3,UU} = U1+U2+K+L

Осталось сложить D1, D2, D3 и соответствующие разряды четверок ("Q1", "Q2" и "Q3"), которые нужно как-то образовать.
Заметим, что при сложении 5 однобитных значений для получения разряда четверок достаточно посмотреть на значение суммы по модулю 4 (S) и на два любых входных значения: если S = 2 или S = 3, то разряд четверок гарантированно 0; если S = 0, то достаточно посмотреть на любые 2 входных бита, чтобы отличить 0 от 4 - хотя бы один из них должен быть равен единице, чтобы в результате было 4; если S = 1, то тоже достаточно посмотреть на любые 2 входных бита, чтобы отличить 1 от 5 - оба должны быть равны единице, чтобы в результате было 5. Таким образом, нужно всего 4 входа для получения разряда четверок при суммировании 5 бит, т.е. Qx=f(Dx, Ux, Y, Z), где Y и Z - любые 2 входа при вычислении {Dx,Ux}. Подчеркнём, что Qx и Dx не могут быть равны единице одновременно.

Тогда, виртуальное Q1 (функцию, зависящую от D1, U1 и любых двух входов первой суммы, пусть A и B) можно сложить с D1 (которое уже есть на входе) и с D3 (пятым входом) с помощью одной функции. В результате переноса в третий бит не возникнет, т.к. Q1 и D1 не могут быть равны единице одновременно (это от меня при решении в уме ускользнуло).

{Q4, D4} = 2*"Q1" + D1 + D3, где Q1 = f(D1, U1, A, B)

Осталось сложить D2, D4, "Q2" и "Q3". С Q2, D2 и D4 поступаем аналогично:

{Q5, DD} = 2*"Q2" + D2 + D4, где Q2 = f(D2, U2, F, G)

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

Осталось сложить "Q3", Q4 и Q5. "Q3" получилось в результате суммирования не пяти, а четырех бит, поэтому для того, чтобы Q3 было единице, D3 и UU должны быть равны нулю, а любой произвольный входной бит - единице. Это можно записать и как Q3 = f(D3, UU, U1, 0).

{OO, QQ} = "Q3" + Q4 + Q5, где Q3 = f(D3, UU, U1, 0).

(Описанное решение принадлежит ftdf, мое решение начинается с
{D1,U1} = A+B+(C^D^E)
{D2,U2} = F+G+(H^I^J)
т.е. пользуется разрывом трехбитных сумматоров на две части, как у kcmamu)