14
\$\begingroup\$

Inspired by recent popularity of nandgame on TNB, and my own previous challenge.

Background

Densely packed decimal (DPD) is a way to efficiently store decimal digits in binary. It stores three decimal digits (000 to 999) in 10 bits, which is much more efficient than naive BCD (which stores one digit in 4 bits).

Conversion table

DPD is designed to easily convert between the bits and the digits by simple pattern matching from top to bottom. Each bit pattern defines how many high digits (8-9) the number has, where they are, and how to move the bits to form the decimal representation.

The following is the conversion table from 10 bits of DPD to three decimal digits. Each decimal digit is represented as 4-bit binary (BCD). Both sides are written left to right from the most significant digit to the least.

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)

Notations

  • The lowercase letters a to i are the bits that are copied to the decimal representation.
  • 0 and 1 are the exact bits in the input or output bit patterns.
  • x bits are ignored in the conversion.

Task

Build a logical circuit using two-input NAND gates to convert 10 bits of DPD to 12 bits of BCD.

Examples

Emphasized bits are the pattern-matching bits.

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
      ^ ^   ^ ^ ^

Scoring & winning criterion

The score is the number of two-input NAND gates used in your circuit. The lowest score wins.

You may define small components in terms of two-input NAND gates, and then use them in your final construction. If a component X includes N two-input NAND gates, each usage of X adds N to your score. For basic logic gates, this means:

  • NOT: +1
  • 2-input AND: +2
  • 2-input OR: +3
  • 2-input XOR: +4
\$\endgroup\$
5
  • \$\begingroup\$ Rolled back Luis' edit because atomic-code-golf is a winning criterion tag and code-challenge is for questions which have a winning criterion not covered by other tags. \$\endgroup\$ Nov 26, 2018 at 15:12
  • \$\begingroup\$ This is still unclear to me. I think there needs to be further description of what the letters a to i mean and the process of converting. Go through the steps, rather than just showing examples and hoping we understand from that. \$\endgroup\$
    – mbomb007
    Nov 26, 2018 at 20:59
  • \$\begingroup\$ @mbomb007, maybe it's just clear to me because one of my languages is SML. That first code block is virtually a reference implementation in a pattern-matching language (although it works better in SMLNJ, which echos the result of each statement, than in MLton). \$\endgroup\$ Nov 26, 2018 at 22:36
  • \$\begingroup\$ @mbomb007 I tried to clarify the pattern-matching nature of the conversion table. Does it help? \$\endgroup\$
    – Bubbler
    Nov 27, 2018 at 0:04
  • 1
    \$\begingroup\$ @Bubbler Yeah, that's helpful \$\endgroup\$
    – mbomb007
    Nov 27, 2018 at 15:00

2 Answers 2

6
\$\begingroup\$

45 39 NANDs (or 43 37)

39 seems to be the absolute minimum, but it is possible to reach 37 NANDs by a trick: By assuming that the largest numbers are correctly encoded.

888, 889, 898, 899, 988, 989, 998, 999 are to be encoded with the 2 MSB as 00, requiring just 37 NANDs for decoding.

However, in the specification for decoding, they are specified to be ignored, meaning they can be anything. It is a reasonable assumption that this freer specification could require even fewer gates, but the opposite is true. 39 gates are required for this. This saving could give real benefits for real circuits.

I also found circuits that were significantly more efficient and faster, containing a few more gates.

No pencil drawn image of the circuit this time. Perhaps later.

The circuit is presented in obvious Verilog code, ready for running with test included.

Verilog code:

// Densely packed decimal (DPD) to decimal, circuit in Verilog.
// Made of just 39 NANDs.
//
// By Kim Øyhus 2019 (c) into (CC BY-SA 3.0.)
// This work is licensed under the Creative Commons Attribution 3.0
// Unported License. To view a copy of this license, visit
// https://creativecommons.org/licenses/by-sa/3.0/
//
// This is my entry to win this Programming Puzzle & Code Golf
// at Stack Exchange: 
// https://codegolf.stackexchange.com/questions/176557/densely-packed-decimal-dpd-to-decimal-with-logic-gates
//
// TASK:
// 3 decimal digits are stored in 10 bits in the DPD format,
// and this circuit transforms them into 3 decimal digits in
// 4 bits each, BCD format.
//
// 39 gates seem to be the smallest possible NAND circuit there is
// for this task, but I can get even lower by a trick, to 37:
// I assume that the largest numbers are correctly encoded.
//   888, 889, 898, 899, 988, 989, 998, 999 are to be encoded
// with the 2 MSB as 00, requiring just 37 NANDs for decoding.
//
//   However, in the specification for decoding, they are specified
// to be ignored, meaning they can be anything. It is a reasonable
// assumption that this freer specification could require even fewer
// gates, but the opposite is true. 39 gates are required for this.
// This saving could give real benefits for real circuits.
//
//   This DPD format seems to be used a lot for storing decimal numbers
// in computers and IO for ALUs, even though it is stored as 12 bits
// per 3 digits inside the ALUs and for other calculations.
// There are many patents for these kinds of circuits, and so I am
// a little skeptical for making a free one for a competition.
// However, the point is to make it as small as possible and of just
// NAND gates, which in itself is not so commercially interesting.


module decode1000 ( in_000, in_001, in_002, in_003, in_004, in_005, in_006, in_007, in_008, in_009, out000, out001, out002, out003, out004, out005, out006, out007, out008, out009, out010, out011 );
  input  in_000, in_001, in_002, in_003, in_004, in_005, in_006, in_007, in_008, in_009;
  output out000, out001, out002, out003, out004, out005, out006, out007, out008, out009, out010, out011;
  wire   wir000, wir001, wir002, wir003, wir004, wir005, wir006, wir007, wir008, wir009, wir010, wir011, wir012, wir013, wir014, wir015, wir016, wir017, wir018, wir019, wir020, wir021, wir022, wir023, wir024, wir025, wir026, wir027, wir028, wir029, wir030, wir031, wir032;

// The 3 bits of 1s goes straight through from input to output.
  assign out000 = in_000;
  assign out004 = in_004;
  assign out008 = in_007;
   
  nand gate001 ( wir001, in_003, in_001 );
  nand gate002 ( wir002, in_002, in_003 );
  nand gate003 ( wir003, wir001, in_006 );
  nand gate004 ( wir004, wir002, in_001 );
  nand gate005 ( wir005, wir001, wir001 );
  nand gate006 ( wir006, in_005, in_001 );
  nand gate007 ( wir007, wir006, in_003 );
  nand gate009 ( wir008, wir004, wir007 );
  nand gate010 ( wir009, wir005, in_006 );
  nand gate011 ( wir010, wir007, wir007 );
  nand gate012 ( wir011, wir009, in_002 );
  nand gate013 ( wir012, wir011, wir009 );
  nand gate014 ( wir013, wir011, wir011 );
  nand gate015 ( wir014, in_008, wir013 );
  nand gate016 ( wir015, in_009, wir013 );
  nand gate017 ( wir016, wir010, wir014 );
  nand gate018 ( wir017, wir014, wir005 );
  nand gate019 ( wir018, wir015, wir015 );
  nand gate020 ( wir019, wir011, wir008 );
  nand gate021 ( wir020, wir019, wir006 );
  nand gate022 ( wir021, wir010, wir018 );
  nand gate023 ( wir022, wir020, wir004 );
  nand gate024 ( wir023, wir016, wir008 );
  nand gate025 ( out001, wir023, wir023 );
  nand gate026 ( out003, wir022, wir022 );
  nand gate027 ( wir024, wir005, wir008 );
  nand gate028 ( wir025, wir012, wir002 );
  nand gate029 ( wir026, wir019, in_003 );
  nand gate031 ( out007, wir024, wir009 );
  nand gate032 ( out011, wir026, wir026 );
  nand gate033 ( wir028, wir017, in_005 );
  nand gate035 ( wir030, wir026, in_008 );
  nand gate036 ( out005, wir028, wir028 );
  nand gate037 ( out009, wir030, wir030 );
  nand gate039 ( wir031, wir026, in_009 );
  nand gate041 ( out010, wir031, wir031 );
  nand gate042 ( wir032, out003, wir018 );
  nand gate043 ( out006, wir003, wir032 );
  nand gate044 ( out002, wir025, wir021 );
endmodule



module test;
   reg  [ 9:0] AB; // input DPD
   wire [11:0] C; // output BCD
    
  decode1000 U1 ( 
  .in_000 (AB[ 0]), 
  .in_001 (AB[ 1]), 
  .in_002 (AB[ 2]), 
  .in_003 (AB[ 3]), 
  .in_004 (AB[ 4]), 
  .in_005 (AB[ 5]), 
  .in_006 (AB[ 6]), 
  .in_007 (AB[ 7]), 
  .in_008 (AB[ 8]), 
  .in_009 (AB[ 9]), 
  .out000 ( C[ 0]),
  .out001 ( C[ 1]),
  .out002 ( C[ 2]),
  .out003 ( C[ 3]),
  .out004 ( C[ 4]),
  .out005 ( C[ 5]),
  .out006 ( C[ 6]),
  .out007 ( C[ 7]),
  .out008 ( C[ 8]),
  .out009 ( C[ 9]),
  .out010 ( C[10]),
  .out011 ( C[11])
  ); 
    
   initial  AB=0;  //unary=0;  binary=0
  always  #1  AB = AB+1;
  initial  begin
    $display("\t\ttime,\tinn 10bit   \tout 3x4bit"); 
    $monitor("%d,\t%b %b %b\t%b %b %b\t %d%d%d",$time, AB[9:7],AB[6:4],AB[3:0], C[11:8], C[7:4], C[3:0],  C[11:8], C[7:4], C[3:0]); 
  end 
  initial  #1023  $finish; 
endmodule


// How I run and test it:
// iverilog -o decode1000 decode1000.v
// vvp decode1000
```
\$\endgroup\$
6
  • \$\begingroup\$ If you assume the input is correctly encoded (the last 24 values don't appear), then you have 288 don't cares in your truth table. If you don't, you have no don't cares, which can only increase the required gates. \$\endgroup\$ Jun 20, 2021 at 17:27
  • \$\begingroup\$ However, when decoding, if you allow yourself to put in any value for those two bits in case of 888 889 898 899 988 989 998 999, you go from no don't cares to 16, which can only decrease the required gates. \$\endgroup\$ Jun 20, 2021 at 17:29
  • \$\begingroup\$ There's no reason to do double-negation of wires. Direct connection of c/f/i will save you six NANDs, bringing it down to 39/37. \$\endgroup\$ Jun 20, 2021 at 17:33
  • \$\begingroup\$ And a BIG thanks to NoLongerBreathedIn who discovered I had forgot to remove 3 double inverters I used as wires. I would have discovered this if I had made a pencil drawing this time too, but I was just too tired of these very hard projects. I have more profitable things to do. As for "don't cares", you are mistaken. If there is a sub circuit which happen to calculate the wanted value at the correct input, but also happen to calculate wrong values at the other less correct inputs, then gates can be saved by using that sub circuit instead. I use effects like this to make my minimal circuits \$\endgroup\$
    – KimOyhus
    Jun 23, 2021 at 22:14
  • \$\begingroup\$ Right. What I meant is this: If you were to write down the full 1024x12 truth tables for the "input correctly encoded" version and for the "input might be wrong" version, the former has 288 Xs, and the latter has every X filled in with a T or F but is otherwise identical. Thus, any circuit for the latter operation will work for the former, so the minimum size circuit for the former can be no bigger. \$\endgroup\$ Jun 23, 2021 at 22:39
5
\$\begingroup\$

65 62 60 58 NANDs

Taking the inputs as i0 to i9 and the outputs as o0 to o9, oa, ob we have

t0 = nand(i6, i7)
t1 = nand(t0, t0)
t2 = nand(i3, i4)
o0 = nand(nand(nand(t2, i3), t1), nand(nand(t2, i8), t1))
t3 = nand(o0, o0)
t4 = nand(i0, t3)
o1 = nand(t4, t4)
t5 = nand(i1, t3)
o2 = nand(t5, t5)
o3 = i2
# Score 13 for the first decimal digit

u0 = nand(i6, i8)
u1 = nand(u0, t0)
u2 = nand(i4, t2)
o4 = nand(nand(nand(u2, u0), u2), nand(u1, t0))
u3 = nand(o4, o4)
u4 = nand(o0, i8)
u5 = nand(u4, u4)
u6 = nand(u3, nand(nand(u5, i0), nand(u4, i3)))
o5 = nand(u6, u6)
u7 = nand(u3, nand(nand(u5, i1), nand(u4, i4)))
o6 = nand(u7, u7)
o7 = i5
# Score 20 for the second decimal digit

o8 = nand(nand(nand(nand(i4, i8), o0), t1), nand(nand(i6, u1), i6))
v2 = nand(o8, o8)
v3 = nand(i6, i6)
v4 = nand(i7, i7)
v5 = nand(v2, nand(nand(i6, nand(nand(i7, i0), nand(v4, i3))), nand(v3, i7)))
o9 = nand(v5, v5)
v6 = nand(v2, nand(nand(i6, nand(nand(i7, i1), nand(v4, i4))), nand(v3, i8)))
oa = nand(v6, v6)
ob = i9
# Score 25 for the third decimal digit

Python test framework to validate the correctness of the construction.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.