Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #31679 > unrolled thread

Szybkie znalezienie zestawu branek w obwodzie

Back to article view | Back to pl.comp.programming

Contents

  Szybkie znalezienie zestawu branek w obwodzie Borneq <borneq@antyspam.hidden.pl> - 2018-07-19 21:25 +0200
    Re: Szybkie znalezienie zestawu branek w obwodzie Borneq <borneq@antyspam.hidden.pl> - 2018-07-19 21:31 +0200
    Re: Szybkie znalezienie zestawu branek w obwodzie Maciej Sobczak <see.my.homepage@gmail.com> - 2018-07-19 13:48 -0700
      Re: Szybkie znalezienie zestawu bramek w obwodzie Borneq <borneq@antyspam.hidden.pl> - 2018-07-19 23:03 +0200
        Re: Szybkie znalezienie zestawu bramek w obwodzie gof@somewhere.invalid (Adam Wysocki) - 2018-07-20 07:54 +0000
          Re: Szybkie znalezienie zestawu bramek w obwodzie Borneq <borneq@antyspam.hidden.pl> - 2018-07-20 21:46 +0200
            Re: Szybkie znalezienie zestawu bramek w obwodzie Wojciech Muła <wojtek.mula@gmail.com> - 2018-07-25 11:05 -0700
        Re: Szybkie znalezienie zestawu bramek w obwodzie Maciej Sobczak <see.my.homepage@gmail.com> - 2018-07-20 14:14 -0700
          Re: Szybkie znalezienie zestawu bramek w obwodzie Borneq <borneq@antyspam.hidden.pl> - 2018-07-21 10:20 +0200
            Re: Szybkie znalezienie a drugie pytanie Borneq <borneq@antyspam.hidden.pl> - 2018-07-21 21:33 +0200
              Re: Szybkie znalezienie a drugie pytanie Borneq <borneq@antyspam.hidden.pl> - 2018-07-22 12:13 +0200
              Re: Szybkie znalezienie a drugie pytanie Sebastian Biały <heby@poczta.onet.pl> - 2018-07-22 22:13 +0200

#31679 — Szybkie znalezienie zestawu branek w obwodzie

Knuth pisał, że jego program znalazł, 10 czy 11 bramek, mniej o jedną 
niż myślał że obwód potrzebuje.
Ale jak widzę, problem ma wielką złożoność, już przy 4 bramkach szuka 
ponad 4 minuty w wersji release.
Bo mam przynajmniej 5 typów - OR, NOR, AND, NAND i XOR, jedno wejście to 
4-10 możliwości + podwojenie, bo może być NOT, cała bramka to 200-400 
możliwości.
Choć widzę, że bramki są symetryczne, to zmniejsza trochę ilości 
możliwości, ale nie tak bardzo , o połowę a nie o pierwiastek.

[toc] | [next] | [standalone]

#31680

W dniu 19.07.2018 o 21:25, Borneq pisze:
> Knuth pisał, że jego program znalazł, 10 czy 11 bramek, mniej o jedną 
> niż myślał że obwód potrzebuje.
> Ale jak widzę, problem ma wielką złożoność, już przy 4 bramkach szuka 
> ponad 4 minuty w wersji release.
może inaczej:
Convert truth tables to circuits.mp4
https://www.youtube.com/watch?v=8sja1RXR_Iw

tworzy dalekie od minimalnego, potem to trzeba w jakiś sposób 
zminimalizować,

[toc] | [prev] | [next] | [standalone]

#31681

On Thursday, July 19, 2018 at 9:25:12 PM UTC+2, Borneq wrote:
> Knuth pisał, że jego program znalazł, 10 czy 11 bramek, mniej o jedną 
> niż myślał że obwód potrzebuje.

To wygląda na ciekawy problem, ale post wygląda na taki ze środka dyskusji a nie z początku. Możesz opisać o co tu chodzi? Czego szukasz i w czym?

-- 
Maciej Sobczak * http://www.inspirel.com

[toc] | [prev] | [next] | [standalone]

#31682 — Re: Szybkie znalezienie zestawu bramek w obwodzie

W dniu 19.07.2018 o 22:48, Maciej Sobczak pisze:
> On Thursday, July 19, 2018 at 9:25:12 PM UTC+2, Borneq wrote:
>> Knuth pisał, że jego program znalazł, 10 czy 11 bramek, mniej o jedną
>> niż myślał że obwód potrzebuje.
> 
> To wygląda na ciekawy problem, ale post wygląda na taki ze środka dyskusji a nie z początku. Możesz opisać o co tu chodzi? Czego szukasz i w czym?
> 
Jest ciekawa rzecz: Digital Electronics Deeds
są przykłady 
ćwiczeń:https://www.digitalelectronicsdeeds.com/learningmaterials/labtopics.html

Jedno z nich trudne:
https://www.digitalelectronicsdeeds.com/learningmaterials/LM/T015/015070_Design_Progr_Logic_Gate/Index.htm

Mam znaleźć ileś bramek, by pasowały do tabeli prawdy.
Jak teraz widzę, najpierw tworzy się zgrubne przybliżenie - obwód który 
ma wielokrotnie więcej niż trzeba, potem przekształca się algebraicznie?

[toc] | [prev] | [next] | [standalone]

#31683 — Re: Szybkie znalezienie zestawu bramek w obwodzie

Borneq <borneq@antyspam.hidden.pl> wrote:

> Mam znaleźć ileś bramek, by pasowały do tabeli prawdy.
> Jak teraz widzę, najpierw tworzy się zgrubne przybliżenie - obwód który 
> ma wielokrotnie więcej niż trzeba, potem przekształca się algebraicznie?

W technikum robiliśmy to metodą Karnaugha.

https://pl.wikipedia.org/wiki/Metoda_Karnaugha

-- 
[ Email: a@b a=grp b=chmurka.net ]
[ Web:   http://www.chmurka.net/ ]

[toc] | [prev] | [next] | [standalone]

#31685 — Re: Szybkie znalezienie zestawu bramek w obwodzie

W dniu 20.07.2018 o 09:54, Adam Wysocki pisze:
> W technikum robiliśmy to metodą Karnaugha.
> 
> https://pl.wikipedia.org/wiki/Metoda_Karnaugha

Dzięki za namiar, są dwie metody, to znaczy jedna odmiana tej samej do 
ręcznego a druga do maszynowego obliczenia.
Czas wykładniczy i dokładne rozwiązanie, podstawa 3 ro zawsze nie 
kilkaset. Poza tym wzmiankowana jest metoda niedokładna heurystyczna, 
szybsza Espresso.

Pytanie - a jak zrobić pierwsze przybliżenie, które będziemy 
optymalizować? Z tego filmiku? czyli wiele AND i OR a może odwrotnie?

[toc] | [prev] | [next] | [standalone]

#31707 — Re: Szybkie znalezienie zestawu bramek w obwodzie

On Friday, July 20, 2018 at 9:46:36 PM UTC+2, Borneq wrote:
> W dniu 20.07.2018 o 09:54, Adam Wysocki pisze:
> > W technikum robiliśmy to metodą Karnaugha.
> > 
> > https://pl.wikipedia.org/wiki/Metoda_Karnaugha
> 
> Dzięki za namiar, są dwie metody, to znaczy jedna odmiana tej samej do 
> ręcznego a druga do maszynowego obliczenia.
> Czas wykładniczy i dokładne rozwiązanie, podstawa 3 ro zawsze nie 
> kilkaset. Poza tym wzmiankowana jest metoda niedokładna heurystyczna, 
> szybsza Espresso.
> 
> Pytanie - a jak zrobić pierwsze przybliżenie, które będziemy 
> optymalizować? Z tego filmiku? czyli wiele AND i OR a może odwrotnie?

Można zapisać funkcję logiczną w postaci BDD, a potem
z BDD przejść na jedną z postaci normalnych (DNF albo CNF)
i już z tego masz obwód.

BDD są dobre, jak masz dużo zmiennych, nawet tysiące.
Chociaż są takie przypadki funkcji, dla których BDD wybucha
pamięciowo.

w.

[toc] | [prev] | [next] | [standalone]

#31686 — Re: Szybkie znalezienie zestawu bramek w obwodzie

> Mam znaleźć ileś bramek, by pasowały do tabeli prawdy.
> Jak teraz widzę, najpierw tworzy się zgrubne przybliżenie - obwód który 
> ma wielokrotnie więcej niż trzeba, potem przekształca się algebraicznie?

Etam. Dzisiaj po prostu użyłbym tej funkcji:

http://reference.wolfram.com/language/ref/BooleanConvert.html

Uwaga reklama: właśnie ta funkcja jest podstawą tego narzędzia:

http://inspirel.com/logicassistant/

Natomiast w szkole faktycznie kazali to robić ręcznie i przy dużej ilości sygnałów nie było to zabawne. :-)

-- 
Maciej Sobczak * http://www.inspirel.com

[toc] | [prev] | [next] | [standalone]

#31687 — Re: Szybkie znalezienie zestawu bramek w obwodzie

W dniu 20.07.2018 o 23:14, Maciej Sobczak pisze:
> http://inspirel.com/logicassistant/

coś takiego:
https://www.digitalelectronicsdeeds.com/learningmaterials/LM/T015/015070_Design_Progr_Logic_Gate/Index.htm

F1 F0 A B f
0  0  0 0 1
0  0  0 1 1
0  0  1 0 1
0  0  1 1 0

0  1  0 0 1
0  1  0 1 0
0  1  1 0 0
0  1  1 1 0

1  0  0 0 0
1  0  0 1 1
1  0  1 0 1
1  0  1 1 0

Jakie będzie pierwsze przybliżenie?

[toc] | [prev] | [next] | [standalone]

#31688 — Re: Szybkie znalezienie a drugie pytanie

W dniu 21.07.2018 o 10:20, Borneq pisze:
> W dniu 20.07.2018 o 23:14, Maciej Sobczak pisze:
>> http://inspirel.com/logicassistant/
> 
> coś takiego:
> https://www.digitalelectronicsdeeds.com/learningmaterials/LM/T015/015070_Design_Progr_Logic_Gate/Index.htm 

Polecam książkę Tadeusz Łuba - Synteza układów logicznych.

Jeszcze pytanie numer 1.5:
jak dla tablicy prawdy znaleźć układ nie bramek ale tranzystorów?
Pytanie numer 2:
dany jest układ w postaci połączeń, jak znaleźć przedstawienie go na 
płaszczyźnie? Co podobnego do programu Graphviz gdzie jest bardzo trudny 
algorytm, ale trochę się różni, bo diagramy .dot mogą mieć ukośne linie 
a nawet łuki, przy czym preferuje się bez zmian kierunku tych linii i 
bez przecinania, natomiast w układach są linie poziome i pionowe 
zmieniające kierunek, przecinające się i jedne leżące nad drugim.

[toc] | [prev] | [next] | [standalone]

#31689 — Re: Szybkie znalezienie a drugie pytanie

W dniu 21.07.2018 o 21:33, Borneq pisze:
> Pytanie numer 2:
> dany jest układ w postaci połączeń, jak znaleźć przedstawienie go na 
> płaszczyźnie? Co podobnego do programu Graphviz gdzie jest bardzo trudny 

Odp 2: szukać należy "Electronic Design Automation"
np. 
https://epdf.tips/electronic-design-automation-synthesis-verification-and-test-systems-on-silicon.html

 > Jeszcze pytanie numer 1.5:
 > jak dla tablicy prawdy znaleźć układ nie bramek ale tranzystorów?

Też ciekawe, nie wiem, czy ktoś się tym zajmował, np najprostszy 
inwerter NOT ma jeden tranzystor, ale jak zastosujemy dla CMOS dla 
tranzystory, to wtedy prąd nie płynie i mamy tylko wysokie/niskie 
napięcie, co oszczędza energię.

Bardzo podoba mi się https://www.falstad.com/circuit/
jest tam indeks przykładów po polsku, dobrze przetłumaczony a nie za 
pomocą translatora.

[toc] | [prev] | [next] | [standalone]

#31693 — Re: Szybkie znalezienie a drugie pytanie

On 7/21/2018 9:33 PM, Borneq wrote:
> jak dla tablicy prawdy znaleźć układ nie bramek ale tranzystorów?

Nie a się ponieważ wtedy nie istnieje binarna tablca prawdy ale 
elektronika analogowa. Tranzystor ma znacząco więcej mozliwości 
podłaczenia, poczynając od pracy jako rezystor a kończać na 
wielobazowych/bramkowych wykonaniach. I wiele innych płaszczyzn pracy 
takich jak nieliniowe wzmocnienia, pojemnosci i indukcje itd. co 
znacząco urozmaica proces projektowania.

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web