Czy ludzie patrzą na zagęszczenie pętli w obwodach boolowskich?

11

Podczas studiów licencjackich EE uczestniczyłem w kilku wykładach, które przedstawiały ładną charakterystykę obwodów boolowskich pod względem liczby zagnieżdżonych pętli. Ze złożonością obwody boolowskie są często uważane za sztylety, ale w rzeczywistości cykle sprzętowe są powszechne. Teraz, modulo kilka szczegółów technicznych dotyczących tego, czym jest pętla i co stanowi zagnieżdżoną pętlę, twierdzenie było w zasadzie, że do implementacji sprzętowej automatu potrzebne są dwie zagnieżdżone pętle, a do implementacji procesora potrzebne są trzy zagnieżdżone pętle. (Mógłbym nie rozumieć tych liczb.)

Niepokoją mnie dwie rzeczy:

  1. Nie było nic takiego jak formalny dowód.
  2. Nigdzie indziej nie widziałem tego.

Czy ktoś badał dokładne tego rodzaju oświadczenia?

W poszukiwaniu nazwiska profesora znalazłem małą stronę internetową i książkę (rozdział 4), która omawia tę taksonomię.

Rodzaj tła : jeśli zastanawiasz się, dlaczego cykle są w ogóle przydatne na prawdziwym sprzęcie, oto prosty przykład. Połącz dwa falowniki w jednym cyklu. (Falownik to bramka, która NIE oblicza funkcji boolowskiej). Obwód ten ma dwie stabilne równowagi (i niestabilną). Bez jakiejkolwiek interwencji z zewnątrz obwód po prostu pozostanie w jednym z dwóch stanów. Możliwe jest jednak wymuszenie obwodu w jednym określonym stanie poprzez zastosowanie zewnętrznego sygnału. Sytuacja wygląda następująco: gdy cykl jest podłączony do zewnętrznego sygnału „czytamy wejście”, a poza tym po prostu „zapamiętujemy ostatnią wartość, którą widzieliśmy”. Jedna pętla pomaga nam zapamiętać różne rzeczy.

cc.complexity-theory reference-request circuit-complexity machine-models ar.hardware-architecture Radu GRIGore
źródło
Być może najlepiej jest to postrzegać jako sposób na ustrukturyzowanie projektu wielkoskalowego obwodu cyfrowego (tak jak dobrym rozwiązaniem byłoby użycie podprogramów w dużym programie komputerowym), a nie tak naprawdę jako formalną dolną granicę? (Rozdział 14 książki, którą połączyłeś, zawiera wiele twierdzeń z dowodami, ale wydaje się, że zakładają one przestrzeganie pewnych zasad przy projektowaniu obwodu?)
Jukka Suomela,
1
Jukka może mieć rację. Weźmy przykład flip-flop (system z jedną pętlą) w porównaniu z maszyną skończoną (system z dwiema pętlami, jak zwykle implementowany). Czy nie możesz wstawić kombinacyjnej logiki przejścia FSM (która nie ma pętli) bezpośrednio do pętli flip-flop? Oczywiście jednobitowy FSM nie jest zbyt interesujący. Może być stały lub przemienny tylko w każdym cyklu. Ten ostatni jest oczywiście przerzutnikiem T z zaciskiem T podłączonym do 1 przewodu. Ale ten sam pomysł działa na bank klapek.
Per Vognsen

Odpowiedzi:

5

Powinieneś rzucić okiem na rozprawę doktorską (później opublikowaną jako monografia) Tomasa Federa: Stabilne sieci i wykresy produktów , gdzie badał złożoność znalezienia stabilnych konfiguracji sieci , które są dokładnie obwodami z „pętlami”, jak wspomniałeś.

Dai Le
źródło