Kombinatoriskt nät

[Exige]

Hej!

Jag har nördat in mig på digitalteknik och tänkte att jag skulle bygga mig några enkla kombinatoriska nät.

Något jag tänkte att jag skulle börja med var att bygga ett enkelt (trodde jag...) kombinatoriskt nätverk för att driva ett sjusegmentselement. Jag såg Ben Eaters pedagogiska video* där han konstruerade just ett sådant på ett kopplingsdäck och blev inspirerad att göra detsamma. Jag tänkte dock designa det själv och även försöka göra det enbart med 2-ingångars NAND-grindar. Satte upp en sanningstabell enligt nedan och började rita Karnaughdiagram.

Det som slog mig efter ett tag var att det är ineffektivt att inte dela logik mellan utsignalerna (a b c d e f g) eftersom en del av logiken blir redundant. Jag sökte lite på nätet och hittade ett schema gjort av Kim Øyhus (https://codegolf.stackexchange.com/ques ... ogic-gates) som endast använder 30 NAND2-grindar. Schemat förbryllar mig något då jag inte hittat metoder för hur man konstruerar kombinatoriska multinivånät med flera utvariabler och få grindar likt detta. Jag har också förgäves försökt att kontakta honom.

Är det någon som vet hur man går tillväga för att konstruera kombinatoriska multinivånät likt detta? Finns det kända metoder eller är det specifika programvaror som kan användas?

För skojs skull började jag skriva på ett C-program för att generera sanningstabeller för alla möjliga konfigurationer av 2-ingångars NAND-grindar där min tanke var att i efterhand kunna söka efter den önskade sanningstabellen och på så sätt hitta det "optimala" (med avseende på antalet grindar) schema för denna uppgift. Problemet är bara att det finns så oerhört många sätt detta kan göras på att det redan vid 5 grindar blir närmar 1 GB (i textformat) av sanningstabeller. Att söka efter 6 grindar blir mer än 10 gånger så dyrt och 7 grindar ytterligare mer än 10 gånger så dyrt. Därmed praktiskt omöjligt att hitta schema med 30 grindar på detta sätt enligt vad jag förstår.

w3 w2 w1 w0 a b c d e f g
0000 1111110
0001 0110000
0010 1101101
0011 1111001
0100 0110011
0101 1011011
0110 1011111
0111 1110000
1000 1111111
1001 1110011
1010 1110111
1011 0011111
1100 1001110
1101 0111101
1110 1001111
1111 1000111

180px-7_Segment_Display_with_Labeled_Segments.svg.png

jjDRrko.jpg

* www.youtube.com/watch?v=7zffjsXqATg

[guckrum]

Ja, det blir snabbt en kombinatorisk explosion som omöjliggör uttömmande sökning som lösningsmetod. Vid logikoptimering har man ofta dessutom bivillkor som begränsad fördröjning eller maximal fan-in eller fan-out (dvs last på in resp utsignalerna) vilket ytterligare ställer till det.
Alla funktioner går att realisera som AND-OR nät (eller NAND-NAND nät), tex via Karnaughdiagram, vilket är praktiskt. Logiksyntes för digital ASIC är däremot ofta baserad på binära beslutsträd, men där mappar man på många många fler typer av grindar.
Det finns säkert mång bra heuristiska metoder beskrivna "där ute", men inget tips på rak arm, tyvärr.

[Lennart Aspenryd]

Kul tanke!

[agehall]

Går det inte att beskriva det man vill göra i Verilog eller VHDL och sedan titta på vad Quartus eller Vivado gör av det? Om man bara beskriver det man vill göra med enkel logik så borde man kunna få ut i princip enbart grindar utan flops i lösningen.

[TomasL]

Det fanns en gång ett kul litet program som hette "Karnough-minimizer" tyvärr finns det inte kvar längre. Det kunde ta ett Karnough-diagram, sanningstabell etc, och göra om det till ett grindnät.

[Klas-Kenny]

TomasL: Det är inte detta du syftar på?
http://k-map.sourceforge.net/

[TomasL]

Ja, men den versionen jag tänker på var betydligt mer avancerad, och kostade lite grand

[MadModder]

Just det där gjorde vi i skolan. Vi fick använda oss av vilka grindar vi ville.
Det jag minns är att vi använde boolesk algebra för att lösa allt, och därefter rita upp resulterande grindnät.

[Exige]

Ja, det blir snabbt en kombinatorisk explosion som omöjliggör uttömmande sökning som lösningsmetod. Vid logikoptimering har man ofta dessutom bivillkor som begränsad fördröjning eller maximal fan-in eller fan-out (dvs last på in resp utsignalerna) vilket ytterligare ställer till det.
Alla funktioner går att realisera som AND-OR nät (eller NAND-NAND nät), tex via Karnaughdiagram, vilket är praktiskt. Logiksyntes för digital ASIC är däremot ofta baserad på binära beslutsträd, men där mappar man på många många fler typer av grindar.
Det finns säkert mång bra heuristiska metoder beskrivna "där ute", men inget tips på rak arm, tyvärr.

Skönt att få en till kommentar på det jag observerat. Kanske kommer kvantdatorer i framtiden att möjliggöra att göra uttömmande sökningar. Fascinerande att ett tillsynes så enkelt schema ska vara såpass svårt att ta fram. Nej, jag har inte heller hittat någon passande heuristisk metod även om jag tror att många dyrare designpaket för ASIC säkert kan detta rätt bra.

[Exige]

Går det inte att beskriva det man vill göra i Verilog eller VHDL och sedan titta på vad Quartus eller Vivado gör av det? Om man bara beskriver det man vill göra med enkel logik så borde man kunna få ut i princip enbart grindar utan flops i lösningen.

Absolut. Kim Øyhus hade även detta i länken ovan. Dock har jag varken tillgång till Quartus eller Vivado. Sedan är jag också intresserad av hur han kommit fram till detta. Hans Verilog är bifogad nedan.

[VISA]

// Hexadecimal 7-segment display driver
// Minimal at 30 NANDs
//
// By Kim Øyhus 2018 (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/ques ... ogic-gates
//
// I am quite sure there are no simpler solutions to this problem,
// except perhaps by changing the symbols on the display,
// but that would be another and different problem.
//
// Since this is actually something useful to do, for instance when
// programming an FPGA to show output, I provide this Verilog code.
//
// As for the minimalism: Of course it was tricky to make.
// It is not comprehensible, since a 7-segment display is
// just a fairly random way of showing numbers, resulting
// in a circuit that is fairly random too.
// And as is typical for these minimal circuits, its logical depth
// is somewhat higher than for close solutions. I guess this is because
// serial is simpler than parallel.
//
// 4 bits of input "in_00?", and 7 bits of output,
// one bit per LED in the segment.
//   A
// F   B
//   G
// E   C
//   D

module display7 ( in_000, in_001, in_002, in_003,  G, F, E, D, C, B, A );
  input in_000, in_001, in_002, in_003;
  output G, F, E, D, C, B, A;
  wire wir000, wir001, wir002, wir003, wir004, wir005, wir006, wir007, wir008, wir009, wir010, wir011, wir012, wir013, wir014, wir015, wir016, wir017, wir018, wir019, wir020, wir021, wir022 ;

  nand gate000 ( wir000, in_000, in_002 );
  nand gate001 ( wir001, in_000, in_000 );
  nand gate002 ( wir002, wir000, in_001 );
  nand gate003 ( wir003, in_001, wir002 );
  nand gate004 ( wir004, wir000, wir002 );
  nand gate005 ( wir005, in_002, wir003 );
  nand gate006 ( wir006, in_003, wir001 );
  nand gate007 ( wir007, wir006, wir004 );
  nand gate008 ( wir008, in_003, wir005 );
  nand gate009 ( wir009, wir005, wir008 );
  nand gate010 ( wir010, in_003, wir008 );
  nand gate011 ( wir011, wir010, wir009 );
  nand gate012 ( wir012, wir010, wir007 );
  nand gate013 ( wir013, wir001, wir011 );
  nand gate014 ( wir014, wir003, wir004 );
  nand gate015 (      G, wir011, wir014 );
  nand gate016 ( wir015, in_003, wir014 );
  nand gate017 ( wir016, wir015, wir013 );
  nand gate018 (      C, wir016, wir012 );
  nand gate019 ( wir017, wir016, wir007 );
  nand gate020 ( wir018, wir003, wir012 );
  nand gate021 ( wir019, wir017, in_003 );
  nand gate022 (      F, wir011, wir017 );
  nand gate023 (      D, wir018, wir017 );
  nand gate024 (      B, wir012,      F );
  nand gate025 ( wir020, wir004, wir018 );
  nand gate026 ( wir021, wir001,      D );
  nand gate027 (      E, wir019, wir021 );
  nand gate028 ( wir022,      D, wir019 );
  nand gate029 (      A, wir020, wir022 );
endmodule

[Exige]

TomasL: Det är inte detta du syftar på?
http://k-map.sourceforge.net/

Intressant! Detta får jag kolla på. En stor fråga är huruvida det klarar av att optimera för att dela logik mellan utvariablerna (a b c d e f g). Annars får vi 7 stycken "optimala" kombinatoriska nät men där ingen logik mellan dem delas. Från det kompletta perspektivet blir det då suboptimalt. Att visuellt se rätt kombination av 7 stycken Karnaugh-diagram tror jag är svårt, men jag kanske har fel här.

Normalt sett får man, av vad jag förstår av Karnaugh-diagram, också endast ut ett två-nivå kombinatoriskt nät realiserat med först en nivå av AND-grindar och sedan en nivå av OR-grindar som kombinerar resultatet från rätt AND-grindar. Att sedan gå till ett fler-nivå NAND2 nät är inte helt trivialt.

[YD1150]

Sök på "Logic Friday", den fungerar bra för att göra om från sanningstabell till en koppling med valfria grindar.

[TomasL]

Ja det var ju rätt trevligt

[4kTRB]

Kombinerat med LogiSim så går det labba fram mycket kul.

[Wihelm]

Skaffa en FPGA om du inte vill koppla massa logiska kretsar manuellt. Vivado är ju fritt för deras enklare FPGA och logik optimering fixar ju programmet.