Test and Complement (TC) Circuits Last edited on 2008-02-12 02:57:08 by stolfi MOST COMPLICATED FUNCTIONS For two wires, the maximum complexity is 3 gates. There are 4 such bifuns: 00 -> 00 0->0 ×0 swap wires 10 -> 01 1->2 0× 01 -> 10 2->1 ×0 11 -> 11 3->3 00 -> 10 0->1 ×0 swap wires and complement wire 0 10 -> 11 1->3 0× 01 -> 00 2->0 ×1 11 -> 01 3->2 00 -> 11 0->3 ×0 swap wires and complement both wires 10 -> 10 1->1 1× 01 -> 01 2->2 ×0 11 -> 00 3->0 00 -> 01 0->2 ×0 swap wires and complement wire 1. 10 -> 00 1->0 1× 01 -> 11 2->3 ×1 11 -> 10 3->1 For three wires, the maximum complexity is 6 gates. There are 32 such bifuns: 000->000 0->0 ×-- if only one '1', rotate bits left; if only two '1's, rotate right 100->010 1->2 0×- 010->001 2->4 ×00 110->101 3->5 1×× 001->100 4->1 ×01 101->011 5->6 1×- 011->110 6->3 111->111 7->7 000->011 0->6 ×-- 100->111 1->7 0×- 010->100 2->1 ×00 110->110 3->3 0×× 001->001 4->4 ×01 101->000 5->0 1×- 011->101 6->5 111->010 7->2 000->110 0->3 100->100 1->1 010->001 2->4 110->101 3->5 001->111 4->7 101->000 5->0 011->011 6->6 111->010 7->2 ×-- 0×- ×10 0×× ×11 1×- 000->011 0->6 100->111 1->7 010->010 2->2 110->000 3->0 001->100 4->1 101->101 5->5 011->110 6->3 111->001 7->4 ×-- 0×- ×10 1×× ×11 1×- 000->101 0->5 100->111 1->7 010->100 2->1 110->001 3->4 001->010 4->2 101->011 5->6 011->110 6->3 111->000 7->0 ×-- 0×- -0× 1×0 ×10 11× 000->011 0->6 100->010 1->2 010->111 2->7 110->001 3->4 001->100 4->1 101->110 5->3 011->101 6->5 111->000 7->0 ×-- 0×- -0× 1×1 ×11 11× 000->110 0->3 100->011 1->6 010->111 2->7 110->101 3->5 001->100 4->1 101->010 5->2 011->000 6->0 111->001 7->4 ×-- 0×- -1× 1×0 ×00 10× 000->101 0->5 100->011 1->6 010->001 2->4 110->000 3->0 001->111 4->7 101->010 5->2 011->110 6->3 111->100 7->1 ×-- 0×- -1× 1×1 ×01 10× 000->000 0->0 100->001 1->4 010->100 2->1 110->011 3->6 001->010 4->2 101->110 5->3 011->101 6->5 111->111 7->7 ×-- 0×- ×01 0×× ×00 1×- 000->101 0->5 100->010 1->2 010->111 2->7 110->110 3->3 001->001 4->4 101->011 5->6 011->000 6->0 111->100 7->1 ×-- 0×- ×01 1×× ×00 1×- 000->110 0->3 100->001 1->4 010->010 2->2 110->011 3->6 001->111 4->7 101->101 5->5 011->000 6->0 111->100 7->1 ×-- 0×- ×11 0×× ×10 1×- 000->101 0->5 100->100 1->1 010->111 2->7 110->000 3->0 001->010 4->2 101->110 5->3 011->011 6->6 111->001 7->4 ×-- 0×- ×11 1×× ×10 1×- 000->011 0->6 100->001 1->4 010->101 2->5 110->000 3->0 001->111 4->7 101->110 5->3 011->100 6->1 111->010 7->2 ×-- 1×- -0× 0×0 ×10 01× 000->110 0->3 100->111 1->7 010->101 2->5 110->011 3->6 001->010 4->2 101->000 5->0 011->100 6->1 111->001 7->4 ×-- 1×- -0× 0×1 ×11 01× 000->111 0->7 100->010 1->2 010->001 2->4 110->011 3->6 001->110 4->3 101->000 5->0 011->101 6->5 111->100 7->1 ×-- 1×- -1× 0×0 ×00 00× 000->111 0->7 100->001 1->4 010->100 2->1 110->101 3->5 001->110 4->3 101->011 5->6 011->000 6->0 111->010 7->2 ×-- 1×- -1× 0×1 ×01 00× 000->011 0->6 100->010 1->2 010->111 2->7 110->101 3->5 001->110 4->3 101->000 5->0 011->100 6->1 111->001 7->4 ×-- -×0 00× 1×× ×01 0×1 000->111 0->7 100->011 1->6 010->100 2->1 110->101 3->5 001->010 4->2 101->000 5->0 011->110 6->3 111->001 7->4 ×-- -×0 00× ×01 0×1 -1× 000->110 0->3 100->111 1->7 010->001 2->4 110->011 3->6 001->100 4->1 101->010 5->2 011->101 6->5 111->000 7->0 ×-- -×0 10× 0×× ×01 1×1 000->111 0->7 100->011 1->6 010->001 2->4 110->000 3->0 001->100 4->1 101->110 5->3 011->101 6->5 111->010 7->2 ×-- -×0 10× ×01 1×1 -1× 000->011 0->6 100->001 1->4 010->100 2->1 110->101 3->5 001->111 4->7 101->010 5->2 011->110 6->3 111->000 7->0 ×-- -×0 0×× 11× ×11 1×1 000->101 0->5 100->111 1->7 010->001 2->4 110->000 3->0 001->110 4->3 101->011 5->6 011->100 6->1 111->010 7->2 ×-- -×0 1×× 01× ×11 0×1 000->110 0->3 100->111 1->7 010->101 2->5 110->001 3->4 001->100 4->1 101->011 5->6 011->000 6->0 111->010 7->2 ×-- -×0 01× ×11 0×1 -0× 000->011 0->6 100->010 1->2 010->101 2->5 110->001 3->4 001->111 4->7 101->000 5->0 011->110 6->3 111->100 7->1 ×-- -×0 11× ×11 1×1 -0× 000->101 0->5 100->011 1->6 010->100 2->1 110->001 3->4 001->111 4->7 101->110 5->3 011->000 6->0 111->010 7->2 ×-- 0-× -×1 10× ×00 1×0 000->110 0->3 100->011 1->6 010->111 2->7 110->001 3->4 001->010 4->2 101->000 5->0 011->101 6->5 111->100 7->1 ×-- 0-× -×1 11× ×10 1×0 000->111 0->7 100->001 1->4 010->101 2->5 110->000 3->0 001->010 4->2 101->011 5->6 011->110 6->3 111->100 7->1 ×-- 1-× -×1 00× ×00 0×0 000->111 0->7 100->010 1->2 010->101 2->5 110->011 3->6 001->100 4->1 101->110 5->3 011->000 6->0 111->001 7->4 ×-- 1-× -×1 01× ×10 0×0 000->101 0->5 100->111 1->7 010->100 2->1 110->011 3->6 001->110 4->3 101->010 5->2 011->000 6->0 111->001 7->4 ×-- -0× 0×1 ×11 01× -×0 000->011 0->6 100->001 1->4 010->111 2->7 110->000 3->0 001->110 4->3 101->010 5->2 011->101 6->5 111->100 7->1 ×-- -0× 1×1 ×11 11× -×0 000->101 0->5 100->010 1->2 010->001 2->4 110->011 3->6 001->111 4->7 101->110 5->3 011->100 6->1 111->000 7->0 ×-- 0×× ×10 01× -×1 10× 000->110 0->3 100->001 1->4 010->111 2->7 110->101 3->5 001->010 4->2 101->011 5->6 011->100 6->1 111->000 7->0 ×-- 0×× ×01 0×1 -1× 1×0 DO EXTRA WIRES HELP? Barring a bug in the code: ${PROGDIR}/${PROG} -size 2 2 -outName foo # optimal (2,2)-TC circuits, general and proper, by size: # # 0 1 1 # 1 7 7 # 2 12 12 # 3 4 4 ${PROGDIR}/${PROG} -size 2 3 -outName foo # optimal (2,3)-TC circuits, general and proper, by size: # # 0 1 1 # 1 23 7 # 2 226 12 # 3 944 4 # 4 486 0 ${PROGDIR}/${PROG} -size 2 4 -outName foo # optimal (2,4)-TC circuits, general and proper, by size: # # 0 1 1 # 1 55 7 # 2 1394 12 # 3 15940 4 # 4 26122 0 # 5 168 0 So extra wires do not help when the input size is 2. What about input size 3? ${PROGDIR}/${PROG} -size 3 3 -outName foo # optimal (3,3)-TC circuits, general and proper, by size: # # 0 1 1 # 1 37 37 # 2 576 576 # 3 5046 5046 # 4 20766 20766 # 5 13862 13862 # 6 32 32 ${PROGDIR}/${PROG} -size 3 4 -maxBifuns 20000000 -maxGates 5 -outName foo # optimal (3,4)-TC circuits, general and proper, by size: # # 0 1 1 # 1 101 37 # 2 5984 576 # 3 259064 5046 # 4 7864104 20766 # 5 ... ... It does not seem to help either (unless it can reduce one of the complexity 6 circuits down to 5 gates).