OT algoritmicka hadanka

[Jan Waclawek]

Miroslav Šinko <sinkomiro@gmail.com> wrote:

> Uloha by sla riesit analogovo s 3x OZ a n + par odpormi. Jeden OZ by
> robil suctovy zosilnovac a dva okienkovy komparator :-)

Hahaha, velmi, velmi pekne... :-)

V podstate je to ekvivalent toho "scitat bity bitoveho pola", ale analogovo a paralelne. Procesor by sa s tym natrapil...

"Michal HW" <michalgregor@centrum.cz> wrote:
> switch( Vstupni_Hodnota ) {
> 
>  case 0x00000001:
>      Navrat = Bit0;
>   break;
> 
>  case 0x00000002:
>      Navrat = Bit1;
>   break;
>  atd.

Toto je co sa tyka narocnosti vsetkych druhov viacmenej ekvivalent toho rotovania (to sa da tiez rozpisat, "unroll"). Procesor obvykle nema efektivnejsi sposob na spracovanie takehoto niecoho nez seria porovnani a skokov.

Pavel KREJCI <krepa76@gmail.com> wrote:
> To by pak mohl zafungovat ten pripad !(x & (x-1)).
> 
> Kaskadovat primo to nepujde, protoze stale musi byt prehled o vsech bitech.
> Jedine co trosku pripomina kaskadu je zapojeni kdy se skaluje po mocninach 2.
> 
> Zakladni bunka pro 2 bity (b0 a b1) ma vystup XOR (necht se jmenuje V)
> a pomocny vystup (necht se jmenuje PV)  PV= !b0 AND !b1
> 
> Pro 4 bity vezmu 2x bunku pro 2 bity a spojim je "spojkou", ktera ma
> nasledujici funkci.
> Vnove = (V1 AND PV2) OR (V2 AND PV1)
> PVnove = PV1 AND PV2
> 
> Pro 8 bitu vezmu 2x strukturu pro 4 bity a spojim je opet "spojkou" z
> predchoziho kroku.
> Pro 16 bitu vezmu ......
> 
> Viz obr. http://krepa.praha12.net/tmp/power2detect.pdf
> 
> Nevim jestli je to dostatecne skalovatelne a akademicke :) Pro jiny
> pocet bitu se holt nastavi nepouzite vstupy do log 0.

Akademicke - neakademicke, je to velmi pekne. Ukazka myslenia v malovstupovej logike, nieco ako je v FPGA. Je to uplne iny pristup nez pre ten procesor - toto je nieco co sa v procesore spravit neda, jednotlive stupne kaskady sa spracovavaju paralelne. To, ze sa v procesore da pouzit pre tento ucel scitacka, je viacmenej "prihodna" nahoda.

Signal Vn sa da nazvat "vo vstupoch tejto kaskady je prave jedna jedicka", signal PV "vsetky vstupy su nula". Da sa urobit este jedna drobna generalizacia: hned prva operacia je vlastne tiez taka ista ako ta kaskadova, ked pre "nulty stupen" kaskady so vstupom X sa urobi V = X a PV = /X.

Este inak by to bolo zrejme optimalne pre velavstupovu logiku typu PLD. To Pascalovske "if x in [1, 2, 4, 8, 16, 32, 64, 128] nie je nic ine ako zapis priamo popisujuci AND/OR maticu. Takze jedna jedina matica vie priamo spracovat tolko bitov vstupu ako je siroky jeho vstupny vektor. A ak je vstupov viac, daju sa kaskadovat presne tak isto ako - v tom predchadzajucom pripade - treba si v dalsej AND/OR matici vyrobit prosty OR vsetkych vstupov, a tento "na kriz" zaviest do AND/OR vyhodnocujuceho "prave jednu jednicku" pre dalsich N bitov. Prejavit by sa to malo na spotrebe makrociel (ktore pomerne priamociaro suvisia s jednotlivymi AND/OR maticami) - ak sa bude ten navrhovy soft otrocky snazit implementovat tu hrozne zlozitu logiku ktora vypadne z pouzitia scitacky, tak zrejme zozerie spustu makrociel; ale to, co som popisal, si vyziada len zopar makrociel.

Takze sa z problemu, ktory mi medzi recou predostrel kolega, vyklula pekna ukazka toho, ako sa v roznych technologiach a s rozlicnym sposobom myslenia daju najst rozdielnym sposobom optimalne riesenia.

wek