Sirkuit Logika Digital - pertanyaan ujian

Saya punya pertanyaan dari ujian yang gagal saya pecahkan:

Saya perlu membangun sirkuit logika digital yang menerima nomor 4 bit dan kembali truejika nomornya 0, 7atau 14. Saya hanya memiliki satu XORgerbang (2 input), satu NOR(3 input), satu NAND(2 input) dan satu decoder 3-ke-8.

Saya pikir pertanyaan itu tidak dapat diselesaikan, saya tidak menemukan kombinasi yang dapat melakukannya. Adakah cara mengatasinya?

Saya menulis sebuah algoritma dalam C # yang mencoba setiap kombinasi yang mungkin dari mereka Nor 3->1 Xor 2->1 Nand 2->1dan Decoder 3->8.

Setelah menjalankannya selama 7½ juta tahun 2 jam, ia mengembalikan 42 Salah. Saya percaya ini membuktikan bahwa pertanyaan tidak memiliki jawaban karena algoritma ini memeriksa setiap kombinasi yang mungkin. :)

Saya diminta untuk menjelaskannya, jadi bagian selanjutnya adalah penjelasan tentang bagian-bagian kode, bagian demi bagian. TL; DR - Anda bisa langsung beralih ke kode di akhir :)

Mari kita bicara tentang jalur input, mereka memiliki status 0 atau 1 dan untuk masing-masing input yang mungkin (0 hingga 15) mereka memiliki nilai yang berbeda:

untuk baris pertama terlihat seperti itu: 0 1 0 1 0 1 ... Yang kedua adalah: 0 0 1 1 0 0 1 1 ... yang ketiga: 0 0 0 0 1 1 1 1 .... seperti biner menghitung ... Anda mendapat ide: P

Jadi saya membuat objek yang mewakili setiap baris di masing-masing negara:

class BitLine{
    bool[] IsActiveWhenInputIs = new bool[16];
}

Seperti yang dikatakan bitLine.IsActiveWhenInputIs [5] mengembalikan apakah saluran aktif ketika inputnya 5.

Ini adalah kode yang membuat jalur input sama sekali:

var bitLineList = new BitLine[6]; // initialize new array of bitLines
for (int i = 0; i < 6; i++) bitLineList [i] = new BitLine(); // initialize each bitLine
for (int i = 0; i < 16; i++)
{
    for (int j = 0; j < 4; j++)
    {
        int checker = 1 << j; // check whether the j-th bit is activated in the binary representation of the number.
        bitLineList[j].IsActiveWhenInputIs[i] = ((checker & i) != 0); // if it's active, the AND result will be none zero, and so the return value will be true - which is what we need :D
    }
}

Kami akan membuat garis bit "selalu benar" dan "selalu salah" - untuk memberikan input "0" atau "1" yang konstan.

for (int i = 0; i < 16; i++){
    bitLineList[4].IsActiveWhenInputIs[i] = false;
    bitLineList[5].IsActiveWhenInputIs[i] = true;
}

Sekarang jika Anda perhatikan, apa yang kami cari sebenarnya adalah bitLine spesifik, yang benar ketika inputnya 0, 7, 14. Mari kita wakili di kelas kami:

var neededBitLine = new BitLine();
for (int i = 0; i < 16; i++){
    neededBitLine.IsActiveWhenInputIs[i] = ((i % 7) == 0); // be true for any number that is devideble by 7 (0,7,14)
}

Ini membuat hal-hal yang sangat sederhana: apa yang sebenarnya kita cari adalah cara untuk "memalsukan" BitLine yang diperlukan ini dari baris bit input (ini adalah bagaimana saya mewakili ke program saya apa yang saya inginkan output saya menjadi).

Sekarang, ini adalah bagaimana kita pergi tentang: setiap kali kita menggunakan beberapa elemen logis pada bitLines kami seperti Xor, Nor, Nandatau bahkan Decoder, kita sebenarnya menciptakan bitline baru \ s. Kami tahu nilai setiap baris dalam setiap input yang mungkin dari 0 hingga 15, sehingga kami dapat menghitung nilai bitLine baru di setiap input yang mungkin juga!

Nand Nor dan Xor semuanya langsung:

void Xor(BitLine b1, BitLine b2, BitLine outputBitLine)
{
    for (var i = 0; i < 16; i++)
    {
        outputBitLine.IsActiveWhenInputIs[i] = b1.IsActiveWhenInputIs[i] != b2.IsActiveWhenInputIs[i];
    }
}

void Nand(BitLine b1, BitLine b2, BitLine outputBitLine)
{
    for (var i = 0; i < 16; i++)
    {
        outputBitLine.IsActiveWhenInputIs[i] = !(b1.IsActiveWhenInputIs[i] && b2.IsActiveWhenInputIs[i]);
    }
}

void Nor(BitLine b1, BitLine b2, BitLine b3, BitLine outputBitLine)
{
    for (var i = 0; i < 16; i++)
    {
        outputBitLine.IsActiveWhenInputIs[i] = !(b1.IsActiveWhenInputIs[i] || b2.IsActiveWhenInputIs[i] || b3.IsActiveWhenInputIs[i]);
    }
}

Untuk setiap input yang mungkin, ini menunjukkan bagaimana BitLine baru akan bertindak.

Menangani decoder sedikit rumit, tetapi idenya adalah "jika bit pada input mewakili angka x dalam biner, maka baris bit output x-th akan benar, sedangkan yang lainnya akan salah. Tidak seperti yang lain fungsi, yang satu ini mendapatkan array dari bitline, dan menambahkan 8 bitline baru ke array.

void Decoder(BitLine b1, BitLine b2, BitLine b3, List<BitLine> lines, int listOriginalLength)
{
    for (int optionNumber = 0; optionNumber < 8; optionNumber++)
    {
        for (var i = 0; i < 16; i++)
        {
            int sum = 0;
            if (b1.IsActiveWhenInputIs[i]) sum += 4;
            if (b2.IsActiveWhenInputIs[i]) sum += 2;
            if (b3.IsActiveWhenInputIs[i]) sum += 1;

            lines[listOriginalLength+optionNumber].IsActiveWhenInputIs[i] = (sum == optionNumber);
        }
    }
}

Sekarang kita memiliki semua elemen dasar kita, jadi mari kita bicara tentang algoritma:

Kami akan melakukan algoritma rekursif, pada setiap kedalaman akan mencoba menggunakan elemen lain (atau \ n dan \ xatau decoder) pada bitline yang saat ini tersedia, dan kemudian mengatur elemen menjadi tidak dapat digunakan untuk kedalaman rekursif berikutnya. Setiap kali kami tiba di bagian bawah dan kami tidak memiliki elemen lagi untuk digunakan, kami akan memeriksa apakah kami memiliki bitline yang kami cari.

Kode ini memeriksa kapan saja apakah grup baris saat ini berisi baris yang kita cari:

bool CheckIfSolutionExist(List<BitLine> lines, int linesLength BitLine neededLine)
{
    for(int i = 0; i<linesLength; i++){
         if (lines[i].CheckEquals(neededLine))
        {
            return true;
        }

    }
    return false;
}

Ini adalah fungsi yang digunakannya untuk memeriksa apakah dua baris sama:

bool CheckEquals(BitLine other)
{
    for (var i = 0; i < 16; i++)
    {
        if (this.IsActiveWhenInputIs[i] != other.IsActiveWhenInputIs[i])
        {
            return false;
        }
    }
    return true;
}

Ok, jadi sekarang untuk bagian utama, ini adalah algoritma utama:

bool Solve(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
    if ((!nand) && (!nor) && (!xor) && (!decoder))
    {
        return CheckIfSolutionExist(lines, listLength, neededLine);
    }
    else
    {
        if (HandleNand(lines, nand, nor, xor, decoder, neededLine,listLength))
        {
            return true;
        }
        if (HandleNor(lines, nand, nor, xor, decoder, neededLine,listLength))
        {
            return true;
        }
        if (HandleXor(lines, nand, nor, xor, decoder, neededLine,listLength))
        {
            return true;
        }
        if (HandleDecoder(lines, nand, nor, xor, decoder, neededLine,listLength))
        {
            return true;
        }
        return false;
    }
}

Fungsi ini menerima daftar bitLines yang tersedia, panjang daftar, boolean yang mewakili apakah setiap elemen saat ini tersedia (xor / nor / nand / decoder), dan bitLine mewakili bitLine yang kami cari.

Pada setiap tahap, ia memeriksa apakah kami memiliki lebih banyak elemen untuk digunakan, jika tidak - memeriksa apakah kami mengarsipkan bitline yang kami butuhkan.

Jika kita masih memiliki lebih banyak elemen, maka untuk setiap elemen ia memanggil fungsi yang seharusnya menangani pembuatan bitLines baru menggunakan elemen-elemen tersebut dan memanggil kedalaman rekursif berikutnya setelahnya.

Fungsi-fungsi handler selanjutnya semuanya sangat mudah, mereka dapat diterjemahkan menjadi "pilih 2 \ 3 dari bitline yang tersedia, dan gabungkan mereka menggunakan elemen yang relevan. Kemudian panggil kedalaman rekursi berikutnya, hanya saja kali ini tidak akan mengandung elemen ini! ".

itulah fungsinya:

bool HandleNand(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
    if (nand)
    {
        for (int i = 0; i < listLength; i++)
        {
            for (int j = i; j < listLength; j++)
            {
                BitLine.Nand(lines[i], lines[j],lines[listLength]);
                if (Solve(lines,listLength+1, false, nor, xor, decoder, neededLine))
                {
                    return true;
                }
            }
        }
    }
    return false;
}

bool HandleXor(List<BitLine> lines,  int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
    if (xor)
    {
        for (int i = 0; i < listLength; i++)
        {
            for (int j = i; j < listLength; j++)
            {
                BitLine.Xor(lines[i], lines[j],lines[listLength]);
                if (Solve(lines,listLength+1, nand, nor, false, decoder, neededLine))
                {
                    return true;
                }

            }
        }
    }
    return false;
}

bool HandleNor(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
    if (nor)
    {
        for (int i = 0; i < listLength; i++)
        {
            for (int j = i; j < listLength; j++)
            {
                for (int k = j; k < listLength; k++)
                {
                    BitLine.Nor(lines[i], lines[j], lines[k],lines[listLength]);
                    if (Solve(lines,listLength+1, nand, false, xor, decoder, neededLine))
                    {
                        return true;
                    }

                }
            }
        }
    }
    return false;
}

bool HandleDecoder(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
    if (decoder)
    {
        for (int i = 0; i < listLength; i++)
        {
            for (int j = i; j < listLength; j++)
            {
                for (int k = j; k < listLength; k++)
                {
                    BitLine.Decoder(lines[i], lines[j], lines[k],lines,listLength);
                    if (Solve(lines,listLength+8, nand, nor, xor, false, neededLine))
                    {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

Dan ini dia, kita sebut saja fungsi ini dengan jalur yang diperlukan yang kita cari, dan memeriksa setiap kemungkinan kombinasi bagian listrik untuk memeriksa apakah mungkin untuk menggabungkannya sedemikian rupa sehingga pada akhirnya satu baris akan dikeluarkan dengan nilai yang dibutuhkan.

* perhatikan bahwa saya menggunakan daftar yang sama setiap saat, jadi saya tidak perlu membuat instance bitlines baru setiap saat. Saya berikan buffer 200 untuk alasan itu.

Ini adalah program lengkap:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp2
{
    public class BitLine
    {
        public bool[] IsActiveWhenInputIs = new bool[16];

        public static void Xor(BitLine b1, BitLine b2, BitLine outputBitLine)
        {
            for (var i = 0; i < 16; i++)
            {
                outputBitLine.IsActiveWhenInputIs[i] = b1.IsActiveWhenInputIs[i] != b2.IsActiveWhenInputIs[i];
            }
        }

        public static void Nand(BitLine b1, BitLine b2, BitLine outputBitLine)
        {
            for (var i = 0; i < 16; i++)
            {
                outputBitLine.IsActiveWhenInputIs[i] = !(b1.IsActiveWhenInputIs[i] && b2.IsActiveWhenInputIs[i]);
            }
        }

        public static void Nor(BitLine b1, BitLine b2, BitLine b3, BitLine outputBitLine)
        {
            for (var i = 0; i < 16; i++)
            {
                outputBitLine.IsActiveWhenInputIs[i] = !(b1.IsActiveWhenInputIs[i] || b2.IsActiveWhenInputIs[i] || b3.IsActiveWhenInputIs[i]);
            }
        }

        public static void Decoder(BitLine b1, BitLine b2, BitLine b3, List<BitLine> lines, int listOriginalLength)
        {
            for (int optionNumber = 0; optionNumber < 8; optionNumber++)
            {
                for (var i = 0; i < 16; i++)
                {
                    int sum = 0;
                    if (b1.IsActiveWhenInputIs[i]) sum += 4;
                    if (b2.IsActiveWhenInputIs[i]) sum += 2;
                    if (b3.IsActiveWhenInputIs[i]) sum += 1;

                    lines[listOriginalLength + optionNumber].IsActiveWhenInputIs[i] = (sum == optionNumber);
                }
            }
        }

        public bool CheckEquals(BitLine other)
        {
            for (var i = 0; i < 16; i++)
            {
                if (this.IsActiveWhenInputIs[i] != other.IsActiveWhenInputIs[i])
                {
                    return false;
                }
            }
            return true;
        }

    }

    public class Solver
    {
        bool CheckIfSolutionExist(List<BitLine> lines, int linesLength, BitLine neededLine)
        {
            for (int i = 0; i < linesLength; i++)
            {
                if (lines[i].CheckEquals(neededLine))
                {
                    return true;
                }

            }
            return false;
        }

        bool HandleNand(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
        {
            if (nand)
            {
                for (int i = 0; i < listLength; i++)
                {
                    for (int j = i; j < listLength; j++)
                    {
                        BitLine.Nand(lines[i], lines[j], lines[listLength]);
                        if (Solve(lines, listLength + 1, false, nor, xor, decoder, neededLine))
                        {
                            return true;
                        }
                    }
                }
            }
            return false;
        }

        bool HandleXor(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
        {
            if (xor)
            {
                for (int i = 0; i < listLength; i++)
                {
                    for (int j = i; j < listLength; j++)
                    {
                        BitLine.Xor(lines[i], lines[j], lines[listLength]);
                        if (Solve(lines, listLength + 1, nand, nor, false, decoder, neededLine))
                        {
                            return true;
                        }

                    }
                }
            }
            return false;
        }

        bool HandleNor(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
        {
            if (nor)
            {
                for (int i = 0; i < listLength; i++)
                {
                    for (int j = i; j < listLength; j++)
                    {
                        for (int k = j; k < listLength; k++)
                        {
                            BitLine.Nor(lines[i], lines[j], lines[k], lines[listLength]);
                            if (Solve(lines, listLength + 1, nand, false, xor, decoder, neededLine))
                            {
                                return true;
                            }

                        }
                    }
                }
            }
            return false;
        }

        bool HandleDecoder(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
        {
            if (decoder)
            {
                for (int i = 0; i < listLength; i++)
                {
                    for (int j = i; j < listLength; j++)
                    {
                        for (int k = j; k < listLength; k++)
                        {
                            BitLine.Decoder(lines[i], lines[j], lines[k], lines, listLength);
                            if (Solve(lines, listLength + 8, nand, nor, xor, false, neededLine))
                            {
                                return true;
                            }
                        }
                    }
                }
            }
            return false;
        }

        public bool Solve(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
        {
            if ((!nand) && (!nor) && (!xor) && (!decoder))
            {
                return CheckIfSolutionExist(lines, listLength, neededLine);
            }
            else
            {
                if (HandleNand(lines, listLength, nand, nor, xor, decoder, neededLine))
                {
                    return true;
                }
                if (HandleNor(lines, listLength, nand, nor, xor, decoder, neededLine))
                {
                    return true;
                }
                if (HandleXor(lines, listLength, nand, nor, xor, decoder, neededLine))
                {
                    return true;
                }
                if (HandleDecoder(lines, listLength, nand, nor, xor, decoder, neededLine))
                {
                    return true;
                }
                return false;
            }
        }
    }

    class Program
    {
        public static void Main(string[] args)
        {
            List<BitLine> list = new List<BitLine>();
            var bitLineList = new BitLine[200];
            for (int i = 0; i < 200; i++) bitLineList[i] = new BitLine();

            // set input bit:
            for (int i = 0; i < 16; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    int checker = 1 << j;
                    bitLineList[j].IsActiveWhenInputIs[i] = ((checker & i) != 0);
                }
            }

            // set zero and one constant bits:
            for (int i = 0; i < 16; i++)
            {
                bitLineList[4].IsActiveWhenInputIs[i] = false;
                bitLineList[5].IsActiveWhenInputIs[i] = true;
            }

            list.AddRange(bitLineList);

            var neededBitLine = new BitLine();
            for (int i = 0; i < 16; i++)
            {
                neededBitLine.IsActiveWhenInputIs[i] = (i%7==0); // be true for any number that is devideble by 7 (0,7,14)
            }

            var solver = new Solver();
            Console.WriteLine(solver.Solve(list, 6, true, true, true, true, neededBitLine));
            Console.ReadKey();
        }
    }
}

Semoga kali ini penjelasan yang valid: P

Ini bukan jawaban, untuk membuang solusi yang paling jelas.

$b_1$$b_2$$b_4$$b_8$

$b_2$$b_4$

$b_1$$b_4$$b_8$

Namun, penyederhanaan dari ungkapan sebelumnya adalah:

itu bukan yang diharapkan:

Untuk alasan ini, saya pikir kemungkinan kesalahan dalam pertanyaan, menjadi "nand" gerbang "atau" satu.

Jawaban yang valid untuk pertanyaan Anda adalah setiap rangkaian yang mengembalikan selalu benar. Karena itu akan mengembalikan true juga jika angka inputnya 0,7, atau 14.

Saya pikir pertanyaannya harus secara eksplisit meminta rangkaian yang ouputs benar jika angka-angka input adalah 0,7, atau 14. Dan itu menghasilkan false jika tidak.

Itu bisa dilakukan. Sebagai petunjuk, dua bit tengah sama untuk semua pola bit ini sehingga xoring mereka akan menghasilkan 0 yang kemudian dapat menjadi input ke decoder dengan dua bit lainnya. Gerbang yang tersisa diterapkan pada tiga output decoder untuk memberikan output bit tunggal yang benar.