Elektroda.pl
Elektroda.pl
X
Elektroda.pl
Proszę, dodaj wyjątek dla www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Mnożenie liczb binarnych (układ iteracyjny)

05 Gru 2012 22:22 5280 13
  • Poziom 10  
    Witam,
    mam do rozwiązania zadanie, w którym trzeba zrobić układ iteracyjny mnożący liczbę binarną 16-bitową razy 3.

    Nie mam pojęcia jak narysować graf do tego układu. Czy mógłby ktoś narysować ten graf?

    Pozdrawiam
  • Poziom 13  
    Nie wiem czy o to chodzi, ale nasuwa mi się odpowiedz. Przesunac liczne o 1 bit w lewo i dodac skladnik.
    Przesuniecie daje pomnozenie przez 2 i do tego dodac wejscie, daje pomnozenie przez 3.
  • Poziom 34  
    Już drugie pytanie o układy iteracyjne i to samo, 'graf'. My dla układów iteracyjnych żadnych grafów nie rysowaliśmy, bo i jakie, i po co. Określaliśmy wejścia i wyjścia dla bloku 1-szego, bloków i-tych i bloku n-tego (1-szy i n-ty zawsze ciut prostsze od i-tego). I po prostu budowaliśmy trzy tablice prawdy, minimalizowaliśmy, i po ptokach.
    Jakie znowu grafy Wam każą. Planu lekcji? Pan profesor niech sam do szkoły wróci albo do fachowych i autoryzowanych podręczników zajrzy...
    P.S.1. ... zamiast do internetowego, bezkarnego bełkotu.
    No bo na przykład:
    https://www.elektroda.pl/rtvforum/viewtopic.ph...yjny&sid=98bf03cc302ce696d8c6ad9f0df09beb
    Jest tam napisane na tym grafie "5 stanów". No to chyba tylko nieważkości umysłu autora posta albo jego nauczyciela.
    P.S.2. O ile jotto <> Ser Cubus... ;)
  • Poziom 10  
    czarutek napisał:
    Już drugie pytanie o układy iteracyjne i to samo, 'graf'. My dla układów iteracyjnych żadnych grafów nie rysowaliśmy, bo i jakie, i po co. Określaliśmy wejścia i wyjścia dla bloku 1-szego, bloków i-tych i bloku n-tego (1-szy i n-ty zawsze ciut prostsze od i-tego). I po prostu budowaliśmy trzy tablice prawdy, minimalizowaliśmy, i po ptokach.
    Jakie znowu grafy Wam każą. Planu lekcji? Pan profesor niech sam do szkoły wróci albo do fachowych i autoryzowanych podręczników zajrzy.


    To samo stwierdziliśmy ostatnio na zajęciach. W internecie prawie nic nie ma z grafami, tylko na slajdach z naszych wykładów. Nie wiem czemu tak nas uczą (Politechnika Gdańska WETI)
  • Poziom 36  
    jotto napisał:
    ... mam do rozwiązania zadanie, w którym trzeba zrobić układ iteracyjny mnożący liczbę binarną 16-bitową razy 3....

    jotto napisał:
    ... Nie wiem czemu tak nas uczą (Politechnika Gdańska WETI)

    Niezly Kindergarden.
    Moze sami nie bardzo wiedza, czego ucza. Sadzac po renomie, jaka ma polska nauka obecnie, nie wykluczalbym takiej mozliwosci.
    Co sie tego "grafu" tyczy, pojecie to jest stosowane w teorii obwodow, teorii automatow i do graficznego opisu roznorakich systemow, ale pomysl uzycia grafow do opisu algorytmow iteracyjnych to prawdziwy przelom w naukach :lol:
    Podejrzewam, ze chodzi po prostu o tzw. FLOW CHART.
  • Poziom 34  
    Może chcą Wam zrobić przedsmak 'tablic przejść' automatów, zwłaszcza asynchronicznych... Ale to zupełnie co innego.
    Jakieś nic tak naprawdę nikomu nie mówiące 'grafy', to tylko mieszają i więcej przyniosą złego, niż dobrego. Układy iteracyjne są układami czysto kombinacyjnymi, więc najlepiej opisują je tablice prawdy. A potem ich poprawna, antyhazardowa minimalizacja.
    Gdybym znał zasady rysowania tych grafów, pewnie bym Ci pomógł. Ale nie znam i nie mam skąd się takich kuriozów dowiedzieć.
    W każdym razie, kolega wyżej proponuje pomnożyć przez łatwe 2 i do wyniku dodać samą siebie, ale przy takiej strategii nie umiem sobie wyobrazić tablic prawdy bloków, jakoś mi to umyka. A podchodząc topornie, trzeba by było ten wynik pośredni mnożenia przez 2 albo dodawania gdzieś przechować.
    Na moje oko, najładniej iteracyjnie i kombinacyjnie byłoby ją po prostu trzykrotnie, ale w jednym kroku, do siebie dodać. Trzeba pamiętać, że wynikowi przybędą dwa bity.

    P.S. O właśnie, Nemo, a może chodzi po prostu o algorytmy działania poszczególnych bloków...
  • Poziom 36  
    czarutek napisał:
    P.S. O właśnie, Nemo, a może chodzi po prostu o algorytmy działania poszczególnych bloków...

    Jakich tam znowu blokow?
    Przeciez jotto napisal wyraznie, ze chodzi o
    Cytat:
    układ iteracyjny mnożący liczbę binarną 16-bitową razy 3

    Iteracja ma jedynie wtedy sens, kiedy uzyty zostanie najzwyklejszy sumator, czyli ordynarne liczydlo, takie jak te dziesietne (z koralikami na drutach), bo przeciez hardware multiplier pracuje bez iteracji.
    Chodzi zatem o prosty algorytm: pomnozyc pozycje (czytaj: przez 1 lub 0, znaczy dodac multiplikand albo nie), przesunac argumenty o 1 bit i znowu to samo, zsumowac wyniki czastkowe, i gotowe. Coz w tym za filozofia? Tego ucza sie dzieci w pierwszej klasie podstawowki, na liczbach dziesietnych!
  • Poziom 34  
    Już mówiąc chociażby tylko "przesunąć argumenty o 1 bit", robisz układ nie iteracyjny w sensie układów logicznych kombinacyjnych, a o czysto kombinacyjny dam głowę tu chodzi.
    Bloki to komórki iteracyjnego układu logicznego kombinacyjnego, połączone ze sobą w jednakowy sposób. Czyli ma tu nie być nic innego oprócz właśnie bloków. Jeśli cokolwiek innego jest dopuszczalne, to to na pewno nie jest żadne zadanie z żadnej szkoły.
    Ma być 18 bloków, bo liczba 16-bitowa pomnożona przez 3 ma już bitów 18. Zakładam, że argument i wynik są tu dla uproszczenia w kodzie Naturalnym Binarnym, rzecz jasna bez znaku.
    Blok bitu najmłodszego ma mieć 1 wejście argumentowe, 1 wyjście wynikowe (zawsze = najmłodszemu bitowi oryginału, o czym na końcu wzmianka) oraz 1 wyjście przeniesienia.
    Blok i-ty ma mieć 1 wejście argumentowe, 1 wejście przeniesienia, 1 wyjście wynikowe oraz 1 wyjście przeniesienia.
    Blok bitu 17-go ma mieć 1 wejście przeniesienia, 1 wyjście wynikowe oraz 1 wyjście przeniesienia.
    Blok bitu najstarszego, czyli 18-go, ma mieć 1 wejście przeniesienia oraz 1 wyjście wynikowe (zawsze = swojemu wejściu przeniesienia. Jest to tutaj najprostszy z wszystkich bloków. Ale nadal stanowi blok!).
    I nic więcej. Żadnego 'przesuwania', żadnych rejestrów, żadnego taktowania, żadnego sumowania (w sensie 'sumatora').
    Wszystkie bloki mają być czysto kombinacyjnymi układami logicznymi!. Zbudowanymi najlepiej wyłącznie z funktorów Zestawu Funkcjonalnie Pełnego. Dla uproszczenia można go sobie rozszerzyć o NAND i NOR, ale kosztem częściejszego hazardu. Żadnych XORów i EXORów nawet, a co dopiero sumatorów! No może jednobitowy by się przydał, ale najmniejsze znam czterobitowe, a i tak sumator jednobitowy sam nie raz prawdopodobnie tu wyjdzie przy syntezie bloków.
    Wynik ma się ustalić po upływie czasu równym sumie czasów ustalania wyniku każdego z bloków, a te z kolei określa suma czasów propagacji zawartych w nich funktorów. W (wieloblokowych zwłaszcza) układach iteracyjnych projektuje się czasem dodatkowe wyjście sygnału bramkującego, o ile hazard wyjścia układu okazuje się nieunikniony, a odbiornik będzie miał charakter sekwencyjny (czy to synchroniczny, czy asynchroniczny).
    I dopiero tak zbudowany iteracyjny, specjalizowany układ logiczny kombinacyjny jest przykładem zadania szkolnego. A w dodatku, dla każdej liczby z dziedziny, działa najszybciej na świecie.
    Dodam jeszcze, że ponieważ jaka by to liczba nie była (parzysta czy nieparzysta), to pomnożona przez 3 daje zawsze liczbę o tej samej parzystości. A więc wyjście wynikowe bloku najmłodszego będzie tu zawsze = swojemu wejściu argumentowemu (w tym bloku zresztą wejściu jedynemu).
  • Poziom 36  
    Czarutek, czy sam choc rozumiesz te swoja mniemanologie? Przeciez to czysty belkot!
    Punkty sobie chcesz nabijac?
    Zamim sie zapedzisz poprzez swawolne redefiniowanie dawno juz ustalonych terminow i zatrujesz sie absurdami wlasnej, domowej roboty, proponuje wrocic do elementarza tychze pojec, zaczynajac np. od http://pl.wikipedia.org/wiki/Iteracja
    EOT!
  • Poziom 34  
    Nemo, pomyliłeś pojęcie układ iteracyjny z pojęciem iteracja. Jesteś widzę już za młody, do wszystkiego komputer Ci potrzebny... ;)
    Twoim zdaniem, jak sądzę, najpierw była ta Twoja iteracja, a dopiero potem układ iteracyjny.
    Twój link z Wikipedii opowiada o iteracji 'młodszej' o jakieś dooobre 40 lat.
    A w dodatku, nie wiem za co, robisz się w stosunku do mnie paskudnie agresywny. A o ile mnie pamięć nie myli, mieliśmy już tu ze sobą sporo do czynienia i to w znaczeniu jak najbardziej pozytywnym. Ale rozumiem - zapomniałeś, a teraz bo bezkarnie.
    I dodam jeszcze, że pierwszymi układami iteracyjnymi były układy czysto analogowe, kiedy to narzędzi do tej Twojej iteracji jeszcze przez lata na świecie nie było.
  • Poziom 13  
    Witam!
    Widzę, że tok poszedł w inną stronę.
    Rozwijając swój wywód postaram się dalej go rozwinąć.

    Co prawda liczby mają być 16 bitowe, lecz ja postaram się to ograniczyć do 4 bitów, gdyż zachowanie się bitów z przedziału powiedzmy od 3-go do 14-go jest podobne.

    Tak więc powiedzmy że mamy 4-ro bitowy argument.
    Kolejną czynnością będzie doprowadzenie go do sumatora.
    Jak już wcześniej powiedziałem, kolejnym składnikiem sumatora, jest argument pomnożony przez 2. Tak się składa, że mnożenie przez 2, 4, 8 itd. jest tym co "tygryski" lubią najbardziej. Wystarczy argument przesunąć o 1 bit w lewo.

    Mnożenie liczb binarnych (układ iteracyjny)

    Idąc dalej tym tropem spróbujmy teraz nasze składniki wprowadzić do sumatora.

    Mnożenie liczb binarnych (układ iteracyjny)

    No dobra. Ale my mamy tylko jeden argument. No to musimy dokonać kolejnego przeonaczenia (czytaj korekty) i wychodzi nam coś takiego.

    Mnożenie liczb binarnych (układ iteracyjny)

    No i zaczynają się pewne problemy. Nie bardzo wiadomo co zrobić z tym bitem opisanym po przesunięciu jako "d4". Nie jestem pewien, ale na mój chłopski łep, to wstawił bym go jako przesunięcie wejściowe.

    Mnożenie liczb binarnych (układ iteracyjny)

    I myślę, że w ten sposób zrealizował bym ten wywód, a może zawód jak wykładowca oczekuje jednak czegoś innego.

    Dalej mógłbym przybliżyć budowę sumatora. Jak to kogoś interesi to pokażę co i jak.

    Na razie tyle na ten temat.
  • Poziom 34  
    Ok, Twoja metoda jest dobra, ale niepotrzebnie wymaga układu iteracyjnego dwuwymiarowego (kaskadowego), podczas gdy zwykłe 3-krotne dodawanie zrealizujemy jednowymiarowym (w jednym kroku).
    Trzeba się tylko dobrze przyjrzeć regułom w bloku i-tym. Bo w pierwszym i w 18-tym od razu je widzimy.
    P.S.1. Jeśli dodasz sumator, to to już nie będzie układ iteracyjny, o jaki chodzi w zadaniu.
    P.S.2. Mam pomysła - zamiast przez 2, pomnóżmy od razu przez 3, czyli przesuńmy nie o jedną, tylko o półtorej pozycji... :D ;)
    To jest klasyczny kruczek w tego typu zadaniach - żeby na przykład sprowadzić tok myślenia właśnie do rzeczy, które "tygryski chciałyby lubić najbardziej"... ;)
    P.S.3. Ok, rozumiem, ale iteracyjność takiego układu polega na tym tylko, że będzie 5 bloków 4-bitowych, a nie 18 1-bitowych. Jestem przekonany, że nie o taki układ w zadaniu chodzi. Można analogicznie, sumatorami 1-bitowymi, ale wtedy kaskadowo, a da się prościej i przede wszystkim szybciej.
  • Poziom 13  
    Tygryski nie lubią mnożyć przez półtora.
    Tygryski lubią mnożenie przez wielokrotność 2 tj. 2, 4, 8, 16 itd.
    Pomnożenie przez 3 można zrobić za pomocą 2 sumatorów, ale wyjdzie taniej za pomocą jednego. Oczywiście projekt (założenie) przekładamy na koszta realizacji.

    Mnożenie liczb binarnych (układ iteracyjny)

    Co do sumatora, to poniżej schemat:

    Mnożenie liczb binarnych (układ iteracyjny)

    Mnożenie liczb binarnych (układ iteracyjny)

    Jak ma ktoś pomysł na to jak nakłonić tygryska aby polubił mnożenie przez 3, to proszę o przedstawienie tego.
  • Poziom 34  
    Pomyślę nad tym dopiero jak się Pytek odezwie, bo go jakby coraz mniej to obchodzi... ;)
    Jedno wiem na pewno - w i-tym bloku mnożenie przez 3 (jak i przez dowolną, inną liczbę całkowitą w KNB) jest na bank określone jednoznacznie i w sposób zupełny. Inaczej, to tego zadania by w ogóle nie było... :D
    Drążąc dalej - mnożenie liczb podanych KNB-nym, jest całkowicie kombinacyjne, ponieważ polega na wielokrotnym dodaniu do siebie stałej. Czyli, jeszcze przedtem, jest na dodatek liniowe.
    Czyli, jaka by ta 16-bitowa liczba nie była, to w sposób zupełny jest określona funkcja we/wy bloku numer "i" układu iteracyjnego, mnożącego tę liczbę między innymi właśnie przez 3.
    Dlatego na przykład, standardowe sumatory, ilo-bitowe by nie były, mają tylko 2 argumenty.
    P.S. Janchar, wszystko ok, tylko funktory typu EXOR i EXNOR nie są podstawowymi. A w dodatku bardzo nasilają hazard. I bardzo często jest tak, że budując układ specjalizowany, wykorzystamy tylko ich 'część', przy okazji w dodatku gdzie tylko się da likwidując hazard metodami ogólnymi jego likwidacji.
    Reasumując - jeśli daną funkcję da się zrealizować układem kombinacyjnym, to nie ma na świecie metod dla niej szybszych.

    Opis sygnałów we/wy

    Xi - wejście bloku "i", bit "i" argumentu X (i = 1..18, przy czym dla argumentu tylko 1..16)
    Pii - wejście bloku "i" przeniesienia z bloku "i-1" (i = 2..18)
    Yi - wyjście bloku "i", bit "i" wyniku Y (i = 1..18)
    Poi - wyjście bloku "i" przeniesienia do bloku "i+1" (i = 1..17). Niech Po1 = 1 oznacza, że przeniesienie z tego bloku jest.

    Tablice prawdy

    Blok 1:
    wiadomo - Y1 = X1, Po1 = X1

    Blok i (i = 2..16):
    czy ktoś dostrzega reguły?

    ...