Signal transition graphs
સિગ્નલ ટ્રાન્ઝિશન ગ્રાફ (એસટીજી) નો ઉપયોગ સામાન્ય રીતે ઇલેક્ટ્રોનિક એન્જિનિયરિંગ અને કમ્પ્યુટર એન્જિનિયરિંગમાં તેમના વિશ્લેષણ અથવા સંશ્લેષણના હેતુઓ માટે એસિંક્રોનસ સર્કિટના ગતિશીલ વર્તનને વર્ણવવા માટે થાય છે. મુખ્ય વ્યાખ્યાઓ અને ઉપયોગો અનૌપચારિક રીતે, એસટીજી એ અસિંક્રોનસ સર્કિટના વર્તનનું ગ્રાફિકલ વર્ણન છે, જેમાં સંકેત આપતી ઘટનાઓ વચ્ચેના કારણભૂત સંબંધો વિશેની માહિતી સીધી રજૂ કરવામાં આવે છે, જે સ્થિતિઓ પર આધારિત વર્ણનોથી વિપરીત છે. આ રીતે, એસ. ટી. જી. સામાન્ય રીતે સમયની આકૃતિઓ દ્વારા રજૂ થતી સર્કિટના વર્ણનને ઔપચારિક બનાવવામાં મદદ કરે છે, જેને કેટલીકવાર તરંગરૂપ પણ કહેવામાં આવે છે. બાદમાં ઇલેક્ટ્રોનિક ઇજનેરો દ્વારા વ્યાપકપણે ઉપયોગમાં લેવાય છે. વધુ ઔપચારિક રીતે, એસટીજી એ અર્થઘટન કરાયેલ (અથવા લેબલ થયેલ) પેટ્રી નેટનો એક પ્રકાર છે, જેના સંક્રમણોને સંકેતોના મૂલ્યોમાં ફેરફારોના નામો સાથે લેબલ કરવામાં આવે છે (સીએફ. સંકેત સંક્રમણો). ઉદાહરણ તરીકે, લેબલિંગનો લાક્ષણિક કેસ એ છે કે જ્યાં સંકેતો દ્વિસંગી હોય છે, તેથી સંક્રમણને સર્કિટમાં સંકેતોની વધતી અને પડતી ધાર તરીકે અર્થઘટન કરવામાં આવે છે. એસટીજી સામાન્ય રીતે સ્ટેટ ગ્રાફ કરતાં એસિંક્રોનસ સર્કિટ્સના વર્તનનું વધુ સઘન વર્ણન આપે છે. સર્કિટના એસટીજી સ્પષ્ટીકરણની જટિલતા સામાન્ય રીતે સર્કિટમાં સંકેતોની સંખ્યામાં રેખીય હોય છે જ્યારે સ્ટેટ ગ્રાફની જટિલતા ઝડપથી વધી શકે છે, એ હકીકતને કારણે કે અસિંક્રોનસ સર્કિટમાં ઉચ્ચ ડિગ્રીની સમવર્તીતા હોય છે. એસટીજીમાં સહવર્તી ઘટનાઓને કારણ-અનુક્રમ સંબંધો દ્વારા રજૂ કરવામાં આવે છે (સીએફ. સાચું સમવર્તી ચલણ) જ્યારે રાજ્ય આલેખમાં સમવર્તી ચલણ ઇન્ટરલીવિંગ દ્વારા રજૂ થાય છે. લિયોનીદ રોસેનબ્લમ (રશિયનમાં) દ્વારા 1981માં સિગ્નલ ગ્રાફ્સ નામ હેઠળ એસટીજીની સૌપ્રથમ દરખાસ્ત કરવામાં આવી હતી. તેમનો વધુ ઔપચારિક રીતે અભ્યાસ કરવામાં આવ્યો હતો અને 1982માં એલેક્સ યાકોવલેવ દ્વારા તેમના પીએચડી થીસીસ (રશિયનમાં) માં અસિંક્રોનસ ઇન્ટરફેસોની ડિઝાઇન પર લાગુ કરવામાં આવ્યા હતા. તેઓ પાછળથી 1985માં બે સ્વતંત્ર સ્રોતોમાં અંગ્રેજીમાં રજૂ કરવામાં આવ્યા હતા, એક રોસેનબ્લમ અને યાકોવલેવ દ્વારા અને બીજું તામ-અન્હ ચુ દ્વારા (અગાઉનું સંસ્કરણ ICCD '85માં રજૂ કરવામાં આવ્યું હતું). ત્યારથી, એસ. ટી. જી. નો સિદ્ધાંત અને વ્યવહારમાં વ્યાપક અભ્યાસ કરવામાં આવ્યો છે, જેના કારણે અસુમેળ નિયંત્રણ સર્કિટના વિશ્લેષણ અને સંશ્લેષણ માટે લોકપ્રિય સોફ્ટવેર સાધનોનો વિકાસ થયો છે, જેમ કે પેટ્રિફી (મુખ્ય વિકાસકર્તાઃ જોર્ડી કોર્ટાડેલ્લા) અને વર્કક્રાફ્ટ (ન્યૂકેસલ યુનિવર્સિટીની ટૂલકિટ). એસિંક્રોનસ સર્કિટ્સની રચનામાં એસ. ટી. જી. નો ઉપયોગ કરવાના વિવિધ ઉદાહરણોમાં, એસિંક્રોનસ ઇન્ટરફેસો, કંટ્રોલર્સ, આર્બિટર્સ અને એનાલોગ-મિક્સ સિગ્નલ સર્કિટ્સના ક્ષેત્રમાં સૌથી વધુ જાણીતા છે, સી. એફ., તાજેતરમાં એસ. ટી. જી. ને કેપેસિટીવ કપલિંગ દ્વારા મધ્યસ્થી કરતી કાર્યકારણને સમાવતી કાર્યકારણ વર્તણૂકના નમૂના સુધી વિસ્તૃત કરવામાં આવી છે, જેમ કે સ્વિચ કેપેસિટર કન્વર્ટર (એસ. સી. સી.) માં ઉપયોગમાં લેવાય છે. વિસ્તરણ અને સંબંધિત નમૂનાઓ એસ. ટી. જી. ઉપરાંત, દ્વિસંગી સંકેતો પર આધારિત, પ્રતીકાત્મક એસ. ટી. જી. પણ છે, જ્યાં સંકેતો બહુ-મૂલ્યવાન હોઈ શકે છે. સમય (વિલંબ) માહિતી ટિપ્પણી સાથે એસટીજી સૌપ્રથમ 1998માં અને પછી 1998માં રજૂ કરવામાં આવ્યા હતા, જ્યાં સમયની મર્યાદાઓ સાથે સર્કિટના વર્તનના વિશ્લેષણના વિચારો પણ સૌપ્રથમ રજૂ કરવામાં આવ્યા હતા, જેને પાછળથી રિલેટિવ ટાઈમિંગ કહેવામાં આવ્યું હતું. પ્લેસ ચાર્ટ નેટ્સમાં અસિંક્રોની અને કોમ્પેક્ટ સ્વરૂપમાં વિક્ષેપોને પકડવા માટે મૂળભૂત અંતર્ગત પેટ્રી નેટ મોડેલોના વિશેષ વિસ્તરણ રજૂ કરવામાં આવ્યા હતા. અસિંક્રોનસ સર્કિટ્સના રાજ્ય-આધારિત નમૂનાઓ અને પેટ્રી નેટ-આધારિત નમૂનાઓ (ઇન્. સી. એસ. ટી. જી.) વચ્ચે એક મહત્વપૂર્ણ જોડાણ થિયરી ઓફ રિજન (સી. એફ.) નો ઉપયોગ કરીને સ્થાપિત કરવામાં આવ્યું છે. રોબર્ટ સ્પ્રોલ, ઇવાન સદરલેન્ડ અને ચાર્લ્સ મોલનારને કારણે કાઉન્ટરફ્લો પાઇપલાઇન પ્રોસેસર માટે એસટીજી મોડેલ અને તેના સર્કિટ અમલીકરણ મેળવવા માટે પ્રદેશોના સિદ્ધાંતનો ઉપયોગ કરવામાં આવ્યો હતો. એસટીજી સાથે નજીકથી સંબંધિત મોડેલોમાંનું એક ચેન્જ ડાયાગ્રામ છે, જે માઈકલ કિશિનેવ્સ્કી, એલેક્સ કોન્ડ્રાતયેવ, એલેક્ઝાન્ડર ટૌબિન અને વિક્ટર વર્ષાવસ્કી દ્વારા પ્રસ્તાવિત છે. ચેન્જ ડાયાગ્રામમાં AND અને OR કાર્યકારણ બંનેને સઘન રીતે મોડેલ કરવામાં સક્ષમ હોવાના ફાયદા છે. પરંતુ તેમની પાસે પસંદગીની દ્રષ્ટિએ વર્ણનાત્મક શક્તિનો અભાવ છે. પેટ્રી જાળીઓ અને બદલાતી આકૃતિઓ વચ્ચેની સરખામણી તેમની વર્ણનાત્મક શક્તિ અને કોઝલ લોજિક જાળીઓના રૂપમાં તેમના એકીકરણની દ્રષ્ટિએ રજૂ કરવામાં આવી છે. એસ. ટી. જી. ને વિવિધ એચ. ડી. એલ. સાથે જોડવામાં આવ્યા છે, ઉદાહરણ તરીકે એસિંક્રોનસ ડિઝાઇનને ટેકો આપવાના હેતુથી વી. એચ. ડી. એલ. (1996) અને વેરિલોગ (2000) સાથેની કડીઓ જુઓ. વી. એચ. ડી. એલ., એસ. ટી. જી. અને પેટ્રી જાળીમાંથી સંશ્લેષણ પ્રવાહમાં મૂકવામાં આવ્યું છે, અને તેવી જ રીતે વેરિલોગ સાથે, જ્યાં એક સાધન વેરિસિન વિકસાવવામાં આવ્યું હતું. તાજેતરમાં એસટીજીને એવા સંકેતો સાથે જોડવામાં આવ્યા છે જે વ્યવહારુ હાર્ડવેર ડિઝાઇનરો માટે સરળ હોવાનું માનવામાં આવે છે, તેથી વેવફોર્મ-ટ્રાન્ઝિશન ગ્રાફ (ડબ્લ્યુટીજી) ના મોડેલનો ઉદભવ થયો છે. તેવી જ રીતે, ડિઝાઇનરો માટે મર્યાદિત રાજ્ય મશીન (એફ. એસ. એમ.) નું મોડેલ હેન્ડલ કરવું સરળ હોઈ શકે છે તે સમજીને, ઉદાહરણ તરીકે, પેટ્રી નેટ અથવા એસ. ટી. જી., ફ્રન્ટ-એન્ડ તરીકે બર્સ્ટ મોડ એફ. એસ. એમ. સાથેની લિંક વિકસાવવામાં આવી છે. વિશ્લેષણ પદ્ધતિઓ આ ક્ષણે, અસિંક્રોનસ સર્કિટ્સના વિશ્લેષણ અને સંશ્લેષણ માટેની સૌથી કાર્યક્ષમ પદ્ધતિઓ પેટ્રી નેટ અનફોલ્ડિંગ્સ પર આધારિત છે-તેનો અભ્યાસ વિક્ટર ખોમેન્કો દ્વારા તેમના પીએચડી થીસીસમાં કરવામાં આવ્યો હતો. તેઓ વર્કક્રાફ્ટ હેઠળ અમલમાં મૂકવામાં આવે છે. અસિંક્રોનસ સર્કિટના પેટ્રી નેટ મોડેલોના અમુક પેટા વર્ગના પ્રદર્શન વિશ્લેષણની તપાસ આઇગુઓ ઝી અને પીટર બીરલ દ્વારા કરવામાં આવી છે. એસિંક્રોનસ સર્કિટ સંશ્લેષણ એસ. ટી. જી. સ્પષ્ટીકરણમાંથી એસિંક્રોનસ સર્કિટના સંશ્લેષણમાં વિવિધ સમસ્યાઓની તપાસ કરવામાં આવી છે. તેમના વર્ગીકરણ માટેની એક રીત એસટીજી સ્પષ્ટીકરણની સ્થિતિ જગ્યાને રજૂ કરવા માટે ઉપયોગમાં લેવાતા વિશ્લેષણ અભિગમો પર આધારિત છે, જેમ કે સ્પષ્ટ સ્થિતિ જગ્યાઓ, અંતર્ગત પેટ્રી જાળીનું અનાવરણ, પેટ્રી જાળીનું માળખાકીય વિશ્લેષણ અને એસટીજીનું સીધું મેપિંગ (વાક્યરચના-સીધું અનુવાદ). આ અભિગમો સામાન્ય રીતે સંશ્લેષણના અલ્ગોરિધમ્સની જટિલતા સાથે જોડાયેલા હોય છે અને તેથી, સાધનોનો રન-ટાઇમ. બીજી બાજુ, આમાંની કેટલીક તકનીકો પેટ્રી જાળીના વર્ગ પર ચોક્કસ નિયંત્રણો લાદે છે. ઉદાહરણ તરીકે, સ્પષ્ટ સ્થિતિ અવકાશ આધારિત પદ્ધતિઓ સામાન્ય રીતે મનસ્વી પેટ્રી જાળી પ્રકાર માટે કામ કરે છે, જ્યારે કેટલીક માળખાકીય પદ્ધતિઓ માટે જરૂરી છે કે અંતર્ગત પેટ્રી જાળી ચિહ્નિત આલેખ અથવા મુક્ત પસંદગીની જાળી હોય. સંપૂર્ણ રાજ્ય કોડિંગ સમસ્યા સર્કિટ અમલીકરણના સંશ્લેષણમાં મુખ્ય જાણીતી સમસ્યાઓમાંની એક છે સંપૂર્ણ રાજ્ય કોડિંગ (CSC). આ સમસ્યાનો ઉકેલ લાવવા માટે વિવિધ પદ્ધતિઓ વિકસાવવામાં આવી છે. સી. એસ. સી. સંતોષ માટે વિશ્લેષણ કરવાની ખાસ કરીને મૂળ રીત એલેક્સ યાકોવલેવ અને પીટર વાનબેકબર્ગન દ્વારા સ્વતંત્ર રીતે વિકસાવવામાં આવેલા જોડાણ સંબંધ અથવા, સમકક્ષ, તાળા સંબંધની કલ્પના પર આધારિત છે. અન્ય પદ્ધતિ પ્રદેશોના સિદ્ધાંતનો ઉપયોગ કરે છે જે પેટ્રી જાળીના તત્વોને રાજ્ય આલેખમાં રાજ્યોના પ્રદેશો સાથે જોડે છે. એલેક્સ સેમેનોવ અને વિક્ટર ખોમેન્કો દ્વારા આંશિક ઓર્ડર અને પેટ્રી નેટ અનફોલ્ડિંગ્સના આધારે CSC શોધ અને રિઝોલ્યુશન માટે સંશ્લેષણ પદ્ધતિઓ વિકસાવવામાં આવી છે. આ પદ્ધતિઓએ વર્કક્રાફ્ટમાં લાગુ કરાયેલ CSC કોર પર આધારિત CSC સમસ્યાઓના અસરકારક વિઝ્યુલાઇઝેશન માટેની પદ્ધતિને ઔપચારિક બનાવવામાં અને અમલમાં મૂકવામાં મદદ કરી છે. જોસેપ કાર્મોના દ્વારા એસટીજી-આધારિત સંશ્લેષણ માટે માળખાકીય એન્કોડિંગ પદ્ધતિઓ વિકસાવવામાં આવી છે. ગતિ-સ્વતંત્ર (અથવા સમાન રીતે અર્ધ-વિલંબ-અસંવેદનશીલ-ક્યૂ. ડી. આઈ.) સર્કિટોના સંશ્લેષણમાં એક મહત્વપૂર્ણ સમસ્યા મર્યાદિત તાર્કિક આધારની અંદર સંશ્લેષણ છે, ઉદાહરણ તરીકે, AND અને OR જેવા માત્ર પ્રતિબંધિત આધાર તર્ક દ્વારોનો ઉપયોગ કરીને-ઉદાહરણ તરીકે, એલેક્સ યાકોવલેવનું કાર્ય જુઓ, જ્યાં E (ઉત્તેજના)-સુસંગતતાની શરત રજૂ કરવામાં આવી હતી જેથી ઉત્તેજના કાર્યો માટે બે-સ્તરના સમ-ઓફ-પ્રોડક્ટ્સ (એસ. ઓ. પી.) તર્ક અને આપેલ એસ. ટી. જી. સ્પષ્ટીકરણના મુખ્ય આઉટપુટ સંકેતો માટે એસ. આર.-લેચનો સમાવેશ કરીને અમલીકરણમાં જોખમ-સ્વતંત્રતાની ખાતરી કરી શકાય. પાછળથી, એલેક્સ કોન્ડ્રાતયેવ અને અન્યોએ મોનોટોનિક કવરની કલ્પનામાં આ સ્થિતિને સામાન્ય બનાવી, જેને સોફ્ટવેર સાધનોમાં તેની અનુભૂતિ મળી. નકારાત્મક દ્વાર પાયા, NAND અને NOR માં સંશ્લેષણની સમસ્યા વધુ પડકારજનક છે. તેના માટે ઘણી પદ્ધતિઓ વિકસાવવામાં આવી છે, જેનું નેતૃત્વ મોટે ભાગે નિકોલે સ્ટારોડોબત્સેવ દ્વારા કરવામાં આવ્યું છે. સંશ્લેષણ માટે એસ. ટી. જી. નું વિઘટન મોટા કદના એસ. ટી. જી. માટે સંશ્લેષણની માપનીયતાની સમસ્યા અને રાજ્ય અવકાશ વિસ્ફોટને ઘટાડવાની જરૂરિયાતોને અંતર્ગત પેટ્રી જાળીના માળખાકીય ગુણધર્મોના સંદર્ભમાં એસ. ટી. જી. ના સંકોચનના આધારે પદ્ધતિઓમાં ઉકેલવામાં આવી છે-જેમ કે મુક્ત પસંદગીના પેટ્રી જાળીને રાજ્ય મશીનો અથવા ચિહ્નિત આલેખમાં વિભાજિત કરવાની રીતો-તેમજ ફેન-ઇન સિગ્નલ સબસેટ્સ (સંકેત માટે ટ્રિગર ઇવેન્ટ્સ). માપનીયતા સાથે વ્યવહાર કરવાનો બીજો અભિગમ એ એસ. ટી. જી. થી એસિંક્રોનસ સર્કિટનું સીધું મેપિંગ છે જેની ડેનિલ સોકોલોવ દ્વારા તપાસ કરવામાં આવી છે. આર્બિટ્રેશન સાથે એસ. ટી. જી. નું સંશ્લેષણ ખાસ કરીને પડકારજનક સમસ્યા એ છે કે આર્બિટર્સ માટે અસિંક્રોનસ સર્કિટનું આપમેળે સંશ્લેષણ કરવું, કારણ કે તેમના એસ. ટી. જી. સ્પષ્ટીકરણમાં તેમની અંતર્ગત પેટ્રી જાળીમાં વર્તણૂકીય સંઘર્ષો હશે. વર્તણૂકીય સંઘર્ષો એવા સંક્રમણોના અસ્તિત્વને સૂચવે છે જે અવિરત હોય. સામાન્ય રીતે, આવા એસટીજીના તર્ક આધારિત અમલીકરણ માટે, સર્કિટ જોખમો માટે સંવેદનશીલ હશે. વર્કક્રાફ્ટમાં મ્યૂટેક્સ સિગ્નલ સંક્રમણોના અર્ધ-સ્વચાલિત નિવેશ, મૂળ સ્પષ્ટીકરણને જાળવી રાખવા જેવી વિશેષ તકનીકો વિકસાવવામાં આવી છે અને તેનો અમલ કરવામાં આવ્યો છે. વધુ વાંચન સંદર્ભો ન્યૂકેસલ યુનિવર્સિટી એસિંક્રોનસ ડિઝાઇન ગ્રુપ પેજ ગ્રુપ ઓન એલ્ગોરિધમ્સ ફોર વીએલએસઆઈ ડિઝાઇન ઓટોમેશન પેજ હાર્ડવેર ડિઝાઇન એન્ડ પેટ્રી નેટ્સ, એડઃ એ. યાકોવલેવ, એલ. લાવગ્નો અને એલ. ગોમ્સ, સ્પ્રિંગર, 2002 ઓટોમેટા (ગણતરી)