Drive tampilan 7-segmen heksadesimal menggunakan gerbang logika NAND

9

Tampilan numerik 7-segmen di mana-mana dapat dengan jelas menampilkan semua 16 digit heksadesimal seperti yang ditunjukkan dalam wikipedia .gif ini

Entri untuk tantangan ini akan membuat diagram sirkuit menggunakan gerbang logika NAND yang mengubah empat bit dari digit hex menjadi input untuk tujuh segmen. Input untuk tampilan 7 segmen biasanya diberi label sebagai berikut: (DP (titik desimal) diabaikan untuk tantangan ini)

masukkan deskripsi gambar di sini

Karenanya sirkuit Anda perlu menyesuaikan diri dengan tabel kebenaran berikut:

Hex   | Hex Input Bit | Output to Segment line:
digit |  3  2  1  0   |  A  B  C  D  E  F  G
------+---------------+-----------------------
   0  |  0  0  0  0   |  1  1  1  1  1  1  0
   1  |  0  0  0  1   |  0  1  1  0  0  0  0
   2  |  0  0  1  0   |  1  1  0  1  1  0  1
   3  |  0  0  1  1   |  1  1  1  1  0  0  1
   4  |  0  1  0  0   |  0  1  1  0  0  1  1
   5  |  0  1  0  1   |  1  0  1  1  0  1  1
   6  |  0  1  1  0   |  1  0  1  1  1  1  1
   7  |  0  1  1  1   |  1  1  1  0  0  0  0
   8  |  1  0  0  0   |  1  1  1  1  1  1  1
   9  |  1  0  0  1   |  1  1  1  1  0  1  1
   A  |  1  0  1  0   |  1  1  1  0  1  1  1
   b  |  1  0  1  1   |  0  0  1  1  1  1  1
   C  |  1  1  0  0   |  1  0  0  1  1  1  0
   d  |  1  1  0  1   |  0  1  1  1  1  0  1
   E  |  1  1  1  0   |  1  0  0  1  1  1  1
   F  |  1  1  1  1   |  1  0  0  0  1  1  1

Saya pikir tabel ini akurat, tapi tolong beri tahu saya jika Anda menemukan kesalahan.

Skor Anda ditentukan oleh jumlah gerbang NAND 2-input yang Anda gunakan (1 poin per gerbang). Untuk menyederhanakan hal-hal, Anda dapat menggunakan gerbang AND, ATAU, TIDAK, dan XOR dalam diagram Anda, dengan skor terkait berikut:

  • NOT: 1
  • AND: 2
  • OR: 3
  • XOR: 4
atomic-code-golf logic-gates Trauma Digital
sumber
tantangan ini tampaknya tentang menggambar diagram sirkuit, dan bukan tentang coding. Juga, nilai poin per gerbang tampak sewenang-wenang (mungkin sengaja), dan menggunakan DAN + TIDAK adalah 3 poin, ketika Anda menyatakan NAND hanya 1.
stokastic
@stokastic Ada banyak tantangan gerbang logika di situs ini, jadi saya menganggap kategori tantangan ini dapat diterima oleh komunitas. Banyak yang menggunakan sistem penilaian yang sama. Logika NAND Saya pikir menjelaskan sistem penilaian ini dengan cukup baik.
Trauma Digital
Cukup adil. Saya belum pernah melihat tag itu sebelumnya. Sepertinya tidak cocok dengan 'teka-teki pemrograman' atau 'golf kode'.
stokastic
Bisakah sirkuit terbelah? Dengan kata lain, dapatkah Anda menyimpan nilai ke variabel dan memanggilnya nanti?
xnor
@xnor Apakah Anda membicarakan hal semacam ini: codegolf.stackexchange.com/a/26235/11259 ? Jika demikian, jawabannya adalah ya.
Digital Trauma

Jawaban:

17

Domino - Total Skor: 243 NAND

  • OR yang digunakan: 61 (masing-masing 3 NAND -> 183 NAND)

  • BUKAN digunakan: 60 (masing-masing 1 NAND -> 60 NAND)

Solusi ini ada dalam domino dan membutuhkan koleksi perangkat lunak yang saya tulis dalam menjawab dua pertanyaan terkait Domino yang diproduksi Martin Büttner ( Golfing for Domino Day dan Domino Circuits ).

Dengan memodifikasi pemecah Sirkuit Domino saya , saya dapat menghasilkan sirkuit domino (file ini juga berisi keluaran pemecah dan kerangka sirkuit) yang terdiri dari OR, dan IFNOTs di mana input pertama selalu BENAR (jadi pada dasarnya TIDAK). Karena tidak ada banyak yang akan cocok di jawaban ini, saya hadir solusi OR dan NOT untuk tabel kebenaran:

A: 1011011111101011
((-1 ifnot (2 or (1 or (-1 ifnot 0)))) or ((-1 ifnot ((-1 ifnot 1) or (-1 ifnot 2))) or ((-1 ifnot (3 or (-1 ifnot (0 or (-1 ifnot 1))))) or (-1 ifnot (0 or ((-1 ifnot 3) or (-1 ifnot (2 or 1))))))))
B: 1111100111100100
((-1 ifnot (3 or 1)) or ((-1 ifnot (3 or (2 or 0))) or (-1 ifnot ((-1 ifnot 3) or ((-1 ifnot (2 or (0 or (-1 ifnot 1)))) or (-1 ifnot ((-1 ifnot 0) or (-1 ifnot 2))))))))
C: 1101111111110100
((-1 ifnot (2 or (-1 ifnot 3))) or ((-1 ifnot (1 or (-1 ifnot 0))) or (-1 ifnot (0 or (-1 ifnot (3 or (1 or (-1 ifnot 2))))))))
D: 1011011011011110
((-1 ifnot (3 or (1 or 0))) or ((-1 ifnot (2 or ((-1 ifnot (3 or 0)) or (-1 ifnot (1 or 0))))) or (-1 ifnot ((-1 ifnot 2) or ((-1 ifnot (3 or 1)) or (-1 ifnot ((-1 ifnot 1) or (-1 ifnot 3))))))))
E: 1010001010111111
((-1 ifnot (3 or (-1 ifnot (2 or (-1 ifnot 1))))) or (-1 ifnot ((-1 ifnot 0) or (-1 ifnot (2 or 1)))))
F: 1000111011111011
((-1 ifnot (3 or (-1 ifnot 1))) or ((-1 ifnot (2 or (0 or (-1 ifnot (1 or (-1 ifnot 3)))))) or (-1 ifnot ((-1 ifnot 0) or (-1 ifnot (2 or (-1 ifnot 1)))))))
G: 0011111011110111
((-1 ifnot (2 or (0 or (-1 ifnot 1)))) or ((-1 ifnot (1 or (-1 ifnot (2 or 0)))) or (-1 ifnot ((-1 ifnot (3 or 2)) or (-1 ifnot (0 or (-1 ifnot 3)))))))

Perhatikan bahwa satu-satunya operasi biner yang digunakan adalah OR dan IFNOT, di mana saya menghitung setiap IFNOT sebagai TIDAK untuk tujuan penilaian

Saya menambahkan tampilan 7-segmen ke ujung sirkuit dan memasukkannya ke dalam simulator domino / gif. Gif yang dihasilkan (yang menunjukkan 'A' sedang ditampilkan) membutuhkan waktu sekitar 2 jam untuk menghasilkan. Karena sirkuit terakhir berukuran 1141 * 517, setiap "sel" diwakili oleh satu piksel. Sel hitam kosong, sel abu-abu memiliki domino berdiri di dalamnya, dan sel putih memiliki domino jatuh di dalamnya. Ini berarti bahwa Anda tidak dapat benar-benar mengetahui apa yang sedang terjadi, dan itu tidak akan membantu jika itu terjepit sama sekali. Sparr dengan ramah menyediakan versi yang jauh lebih kecil dari gif asli saya (650kB), jadi ini dia!

Animasi

Di bawah ini adalah bingkai terakhir dari animasi untuk input 1010 ('A') seperti di atas. Anda dapat melihat input di paling kiri, kabel listrik di atas, papan tombol mengambil sebagian besar ruang, 7 potongan logika individu (ini adalah representasi domino dari fungsi di atas) di sebelah kiri papan switch, dan untuk paling kanan adalah tampilan 7-segmen itu sendiri. Saat ini berjalan, masing-masing segmen menyala secara kasar pada saat yang sama, jadi Anda tidak dapat melihatnya terlalu lama dengan beberapa segmen menyala menunggu yang lain menyala.

Bingkai animasi terakhir

Lihat animasi dalam kemuliaan penuh di sini (36MB) atau di sini (650kB, milik Sparr) (salinan yang lebih kecil jauh lebih kecil, tetapi browser saya sepertinya suka melewatkan bingkai yang merusak keindahan sehingga saya meninggalkan yang asli dengan demikian)

Detail tampilan 7-segmen dapat dilihat di sini ('1' ditunjukkan)

VisualMelon
sumber
3
+1 untuk kepastian belaka mengendarai tampilan 7-segmen dengan kartu domino!
Digital Trauma
Itu luar biasa ... Seseorang harus mencoba ini di kehidupan nyata
Beta Decay
11

30 NANDs

Saya cukup yakin tidak ada solusi yang lebih sederhana untuk masalah ini, kecuali mungkin dengan mengubah simbol pada layar, tetapi itu akan menjadi masalah lain dan berbeda.

Karena ini sebenarnya sesuatu yang berguna untuk dilakukan, misalnya ketika memprogram FPGA untuk menampilkan keluaran, saya memberikan kode Verilog.

Adapun minimalis: Tentu saja itu sulit untuk dibuat. Ini tidak dapat dipahami, karena tampilan 7-segmen hanyalah cara yang cukup acak bahwa manusia menunjukkan angka, menghasilkan sirkuit yang cukup acak juga. Dan seperti tipikal untuk rangkaian minimal ini, kedalaman logisnya agak lebih tinggi daripada untuk solusi dekat. Saya kira ini karena serial lebih sederhana daripada paralel.

Penundaan transmisi ditunjukkan oleh posisi ke bawah dari setiap gerbang NAND pada lembar.

Driver tampilan 7-segmen heksadesimal minimal

Kode Verilog:

// 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: 
// /codegolf/37648/drive-a-hexadecimal-7-segment-display-using-nand-logic-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

Kim Øyhus

KimOyhus
sumber
Ini adalah solusi yang sangat mengesankan! Mengapa Anda begitu percaya diri sehingga seseorang tidak dapat melakukan lebih baik dari 30? 37 sudah tampak "sangat berkurang", imo.
Alex Meiburg
Terima kasih. Saya mencari di luar solusi ini, menggunakan lebih banyak waktu untuk itu daripada menemukan solusi itu sendiri, dan tidak ada apa pun di sana. Kemungkinan saya melewatkan sesuatu yang lebih baik sangat kecil. Ini adalah argumen statistik.
KimOyhus
7

Menggunakan ~ untuk NOT dan N untuk NAND, pencarian komputer (tanpa berbagi istilah antara output) menemukan solusi dengan 82 NANDs tanpa berbagi. Mencari istilah berbagi secara manual akan menurunkannya menjadi 54 NAND, dan pencarian komputer yang mencakup pembagian lebih lanjut menguranginya menjadi 37 NAND. Minimal mungkin bahkan lebih rendah, karena metode ini tentu tidak lengkap.

Inilah program yang membuat ulang tabel di atas. Setiap baris diberi label dengan NANDS untuk output itu.

#include <stdio.h>

int N(int x, int y) { return 1 & ~(x & y); }

void main(void)
{
    int i0, i1, i2, i3;
    for (i3 = 0; i3 <= 1; i3++) {
    for (i2 = 0; i2 <= 1; i2++) {
    for (i1 = 0; i1 <= 1; i1++) {
    for (i0 = 0; i0 <= 1; i0++) {
            printf("%d %d %d %d : %d %d %d %d %d %d %d\n", i3, i2, i1, i0,
    /* 14 */        N(N(N(i3, N(i2, i1)), N(N(i2, i0), ~i1)), N(N(i2, N(i3, N(i3, i0))), N(i0, N(i3, N(i3, i1))))),
    /* 12 */        N(N(N(i3, i0), N(i2, N(i1, i0))), N(~i1, N(N(i3, i0), N(~i3, N(i2, i0))))),
    /* 10 */        N(N(i0, N(i3, i1)), N(N(i3, i2), N(i1, N(i1, N(~i3, ~i2))))),
    /* 16 */        N(N(N(i2, i1), N(N(i3, i0), N(i2, i0))), N(N(i0, N(i1, ~i2)), N(N(i3, i2), N(N(i3, i1), N(i2, N(i2, i1)))))),
    /*  7 */        N(N(i3, i2), N(N(i2, N(i2, i1)), N(i0, N(i3, i1)))),
    /* 11 */        N(N(i3, N(i2, N(i3, i1))), N(N(i1, N(i2, N(i2, i0))), N(i0, N(i2, ~i3)))),
    /* 12 */        N(N(i3, i0), ~N(N(i1, N(i2, i0)), N(N(i3, i2), N(~i3, N(i2, N(i2, i1)))))) );
    } } } }
}

Dan inilah hasilnya:

0 0 0 0 : 1 1 1 1 1 1 0
0 0 0 1 : 0 1 1 0 0 0 0
0 0 1 0 : 1 1 0 1 1 0 1
0 0 1 1 : 1 1 1 1 0 0 1
0 1 0 0 : 0 1 1 0 0 1 1
0 1 0 1 : 1 0 1 1 0 1 1
0 1 1 0 : 1 0 1 1 1 1 1
0 1 1 1 : 1 1 1 0 0 0 0
1 0 0 0 : 1 1 1 1 1 1 1
1 0 0 1 : 1 1 1 1 0 1 1
1 0 1 0 : 1 1 1 0 1 1 1
1 0 1 1 : 0 0 1 1 1 1 1
1 1 0 0 : 1 0 0 1 1 1 0
1 1 0 1 : 0 1 1 1 1 0 1
1 1 1 0 : 1 0 0 1 1 1 1
1 1 1 1 : 1 0 0 0 1 1 1

Dan berikut ini persamaan yang setara, istilah berbagi yang membuatnya menjadi 54 NAND:

    /* 1 */ int z1 = 1 - i1;
    /* 1 */ int z2 = 1 - i2;
    /* 1 */ int z3 = 1 - i3;

    /* 1 */ int n_i2_i0 = N(i2, i0);
    /* 1 */ int n_i2_i1 = N(i2, i1);
    /* 1 */ int n_i3_i0 = N(i3, i0);
    /* 1 */ int n_i3_i1 = N(i3, i1);
    /* 1 */ int n_i3_i2 = N(i3, i2);

    /* 1 */ int n_i0_n_i3_i1 = N(i0, n_i3_i1);
    /* 1 */ int n_i2_n_i2_i1 = N(i2, n_i2_i1);

            printf("%d %d %d %d : %d %d %d %d %d %d %d\n", i3, i2, i1, i0,
    /* 9 */ N(N(N(i3, n_i2_i1), N(n_i2_i0, z1)), N(N(i2, N(i3, n_i3_i0)), N(i0, N(i3, n_i3_i1)))),
    /* 7 */ N(N(n_i3_i0, N(i2, N(i1, i0))), N(z1, N(n_i3_i0, N(z3, n_i2_i0)))),
    /* 5 */ N(n_i0_n_i3_i1, N(n_i3_i2, N(i1, N(i1, N(z3, z2))))),
    /* 8 */ N(N(n_i2_i1, N(n_i3_i0, n_i2_i0)), N(N(i0, N(i1, z2)), N(n_i3_i2, N(n_i3_i1, n_i2_n_i2_i1)))),
    /* 2 */ N(n_i3_i2, N(n_i2_n_i2_i1, n_i0_n_i3_i1)),
    /* 8 */ N(N(i3, N(i2, n_i3_i1)), N(N(i1, N(i2, n_i2_i0)), N(i0, N(i2, z3)))),
    /* 6 */ N(n_i3_i0, ~N(N(i1, n_i2_i0), N(n_i3_i2, N(z3, n_i2_n_i2_i1)))) );

Dan inilah solusi 37 NAND:

    x0fff =  N(i3, i2);
    x33ff =  N(i3, i1);
    x55ff =  N(i3, i0);
    x0f0f =  not(i2);
    x3f3f =  N(i2, i1);
    x5f5f =  N(i2, i0);
    xcfcf =  N(i2, x3f3f);
    xf3f3 =  N(i1, x0f0f);
    x5d5d =  N(i0, xf3f3);
    xaaa0 =  N(x55ff, x5f5f);
    xfc30 =  N(x33ff, xcfcf);
    xd5df =  N(x3f3f, xaaa0);
    xf3cf =  N(x0fff, xfc30);
    xaeb2 =  N(x5d5d, xf3cf);
    x7b6d =  N(xd5df, xaeb2);
    xb7b3 =  N(i1, x7b6d);
    xf55f =  N(x0fff, xaaa0);
    xcea0 =  N(x33ff, xf55f);
    x795f =  N(xb7b3, xcea0);
    xd7ed =  N(xaeb2, x795f);
    xfaf0 =  N(x55ff, x0f0f);
    xae92 =  N(x55ff, x7b6d);
    xdd6d =  N(x33ff, xae92);
    x279f =  N(xfaf0, xdd6d);
    xaf0f =  N(i2, x55ff);
    x50ff =  N(i3, xaf0f);
    xef4c =  N(xb7b3, x50ff);
    x1cb3 =  N(xf3cf, xef4c);
    xef7c =  N(xf3cf, x1cb3);
    xfb73 =  N(i1, x279f);
    x2c9e =  N(xd7ed, xfb73);
    xdf71 =  N(xf3cf, x2c9e);
    xdd55 =  N(i0, x33ff);
    xf08e =  N(x0fff, xdf71);
    x2ffb =  N(xdd55, xf08e);
    x32ba =  N(xcfcf, xdd55);
    xfd45 =  N(x0fff, x32ba);

    printf("%d %d %d %d : %d %d %d %d %d %d %d\n", i3, i2, i1, i0,
            xd7ed, x279f, x2ffb, x7b6d, xfd45, xdf71, xef7c);
    } } } }
AoneOne
sumber
2
Anda harus memiliki tajuk bangga dengan "37 NANDs". Posting Anda terlalu sederhana tanpa itu.
KimOyhus
4

197 NANDs

Karena ini adalah tantangan gerbang logika pertama saya. itu tidak banyak golf, dan mungkin bukan solusi terkecil. Saya tidak menggunakan split sirkuit di sini.

A = OR(AND(d, NOT(AND(a, XOR(c, b)))), AND(NOT(d), NOT(AND(NOT(b), XOR(a, c)))))
B = AND(OR(OR(NOT(c), AND(NOT(d), NOT(XOR(b, a)))), AND(d, a)), NOT(AND(AND(d, b), a)))
C = OR(AND(NOT(c), NOT(AND(AND(NOT(d), b), NOT(a)))), AND(c, OR(NOT(d), AND(AND(d, NOT(b)), a))))
D = AND(OR(OR(OR(a, c), AND(AND(NOT(d), NOT(c)), NOT(a))), AND(AND(d, NOT(c)), NOT(b))), NOT(OR(AND(AND(NOT(d), NOT(b)), XOR(c, a)), AND(AND(c, b), a))))
E = OR(AND(NOT(a), NOT(AND(AND(NOT(d), c), NOT(b)))), AND(d, NOT(AND(AND(NOT(c), NOT(b)), a))))
F = AND(OR(OR(d, c), AND(NOT(b), NOT(a))), NOT(AND(AND(c, a), XOR(d, b))))
G = AND(OR(OR(d, c), b), NOT(OR(AND(AND(NOT(d), c), AND(b, a)), AND(AND(d, c), AND(NOT(b), NOT(a))))))
  • 36 BUKAN digunakan, 36 NAND
  • 41 ANDs digunakan, 84 NANDs
  • 19 OR digunakan, 57 NAND
  • 5 XOR digunakan, 20 NAND

Jika saya benar, skor saya adalah 197 .

Selama tantangan ini, saya membuat kode JavaScript sederhana untuk menguji gerbang saya.

function NOT(a){return !a}function AND(a,b){return a&b}function OR(a,b){return a|b}function XOR(a,b){return a^b}
for(d=0;d<=1;d++){for(c=0;c<=1;c++){for(b=0;b<=1;b++){for(a=0;a<=1;a++){console.log(""+d+c+b+a,
    // Enter your gate here
    // OR(AND(d, NOT(AND(a, XOR(c, b)))), AND(NOT(d), NOT(AND(NOT(b), XOR(a, c)))))
)}}}}

Salin dan modifikasi gerbang, dan tempel ke konsol browser Anda, atau Node.js REPL.

Camilan
sumber