एक एल्गोरिथ्म या बीजीय व्यंजक (algebraic expression) को Signal Flow Graph (SFG) के माध्यम से विज़ुअल रूप से दर्शाया जा सकता है। इस अध्याय में, हम:

• दिखाएंगे कि एक signal flow graph कैसा दिखता है।
• एक signal flow graph और उसके घटकों (components) को विस्तार से परिभाषित करेंगे।
• Fibonacci सीरीज़ के लिए एक signal flow graph बनाएंगे।

एक signal flow graph कैसा दिखता है?

मान लीजिए कि एक एल्गोरिथ्म है जो दो वेरिएबल्स, $a$ और $b$, को इनपुट के रूप में लेता है और उनके योग (sum) को, जिसे $y$ द्वारा दर्शाया गया है, आउटपुट के रूप में देता है:

यहाँ, $y$ वह वेरिएबल है जो $a$ और $b$ के योग को दर्शाता है।

उदाहरण:

ऑपरेशन $y=a+b$ को विज़ुअल रूप से निम्नलिखित तरीके से दर्शाया जा सकता है:

या, यदि ऑपरेशन संदर्भ (context) से स्पष्ट नहीं है, तो हम इसे स्पष्ट रूप से (explicitly) दिखा सकते हैं, जैसे कि:

इस प्रस्तुति (representation) को Signal Flow Graph (SFG) कहा जाता है। एक signal flow graph किसी एल्गोरिथ्म का एक विज़ुअल रूप है जो विभिन्न इनपुट्स (यहाँ, $a$ और $b$) लेता है और संबंधित आउटपुट (यहाँ, $y$) उत्पन्न करता है। अब हम एक SFG के घटकों (components) की जांच करेंगे।

SFG के घटक (Components)

एक signal flow graph मुख्य रूप से nodes और edges से बना होता है, जहाँ nodes वेरिएबल्स को दर्शाते हैं और उन्हें बिंदुओं (dots) के रूप में चित्रित किया जाता है, और edges रेखाखंड (line segments) होते हैं जो किन्हीं दो nodes को जोड़ते हैं। निम्नलिखित SFG में, तीन nodes हैं, $a$, $b$, और $y$। यहाँ दो edges भी हैं: एक जो node $a$ को node $y$ से जोड़ता है, और दूसरा जो node $b$ को node $y$ से जोड़ता है।

Node $a$ और node $b$ को input nodes कहा जाता है, और $y$ को एक output node कहा जाता है।

एक input node में केवल outgoing edges होते हैं। एक output node में केवल incoming edges होते हैं। एक mixed node में incoming और outgoing दोनों edges हो सकते हैं। हम जल्द ही mixed nodes से जुड़े उदाहरण देखेंगे।

एक edge एक विशिष्ट ऑपरेशन को दर्शाता है। उदाहरण के लिए, ऊपर दिए गए ग्राफ में, यदि edges जोड़ (addition) को दर्शाते हैं, तो आउटपुट वेरिएबल $y$ इस प्रकार दिया जाता है:

यदि ऑपरेशन एक तुलना (comparison) है, तो $y$ इस प्रकार दिया जाता है:

या

यह इस बात पर निर्भर करता है कि किस तुलना (comparison) ऑपरेशन का उपयोग किया गया है।

किसी edge पर मौजूद तीर (arrow) उसकी दिशा को इंगित करता है, जो यह निर्धारित करता है कि किसी node के संदर्भ में वह incoming edge है या outgoing edge। यदि कोई दिशा निर्दिष्ट नहीं की गई है, तो हम बाएं-से-दाएं दिशा मान लेते हैं; अर्थात, edge बाईं ओर के node से outgoing है और दाईं ओर के node पर incoming है।

एक SFG यह वर्णन करता है कि nodes और edges के माध्यम से वेरिएबल्स एक-दूसरे के साथ कैसे इंटरैक्ट करते हैं।

एक mixed node वह node होता है जिसमें incoming और outgoing दोनों edges होते हैं, जैसे कि नीचे दिए गए चित्र में nodes $p$ और $q$।

एक mixed node या output node हमेशा अपने incoming edges के परिणाम को दर्शाता है, जो उन edges से जुड़े ऑपरेशन्स पर निर्भर करता है। आइए हम निम्नलिखित SFG पर विचार करें:

यहाँ, यदि edges से जुड़ा ऑपरेशन जोड़ (addition) है, तो

Node $p$, nodes $a$ और $b$ से आने वाले मानों (values) का योग है। Node $q$, nodes $c$ और $d$ से आने वाले मानों का योग है। अंततः, node $y$, nodes $p$ और $q$ से आने वाले मानों का योग है।

Weighted Edges

एक edge को एक weight असाइन किया जा सकता है। weight एक फैक्टर है जो edge से जुड़े ऑपरेशन के लागू होने से पहले एक node के मान (value) को गुणा (multiply) करता है। इसे समझने के लिए आइए हम निम्नलिखित उदाहरण देखें।

उपरोक्त ग्राफ में, weight $3$, $a$ को गुणा करता है, और weight $7$, $b$ को गुणा करता है। ऑपरेशन को जोड़ (addition) माना गया है।

जोड़ (addition) ऑपरेशन फिर यह आउटपुट उत्पन्न करता है:

यदि किसी edge को कोई weight असाइन नहीं किया गया है, तो weight को $1$ मान लिया जाता है, जिसका अर्थ है कि node के मान को $1$ के फैक्टर से गुणा किया जाता है। उदाहरण के लिए, नीचे दिए गए SFG में जहाँ ऑपरेशन को जोड़ (addition) के रूप में परिभाषित किया गया है:

$y$ का मान इस प्रकार दिया जाता है:

किसी edge पर नेगेटिव (negative) weights का उपयोग करके घटाव (subtraction) प्राप्त किया जा सकता है। उदाहरण के लिए, नीचे दिए गए SFG में:

$y$ का मान है:

Signal flow graphs का उपयोग विभिन्न प्रकार के एल्गोरिदम और समस्याओं को दर्शाने और व्याख्या करने (interpret) के लिए किया जा सकता है। आइए आगे हम एक उदाहरण देखें।

एक SFG के रूप में Fibonacci सीरीज़

प्रसिद्ध Fibonacci सीरीज़ पर विचार करें:

सीरीज़ का प्रत्येक एलिमेंट (element) पिछले दो एलिमेंट्स का योग होता है, जिसमें पहला और दूसरा एलिमेंट क्रमशः $0$ और $1$ होते हैं।

Fibonacci अनुक्रम (sequence) को एक SFG के रूप में दर्शाया जा सकता है जिसमें edges जोड़ (addition) ऑपरेशन करते हैं। आइए $13$ तक के एलिमेंट्स के लिए Fibonacci SFG बनाएं। मान लें कि:

ये दो वेरिएबल्स, $a$ और $b$, हमारे SFG के input nodes हैं। अगला एलिमेंट,

इसे इस प्रकार दर्शाया जा सकता है:

अगले एलिमेंट के लिए,

हम दो edges और एक node $d$ जोड़ते हैं ताकि हमें यह प्राप्त हो सके:

इसी तरह, node $e=c+d=1+2=3$ को इस प्रकार दर्शाया जाता है:

हम SFG का निर्माण तब तक जारी रखते हैं जब तक हम इस output node तक नहीं पहुँच जाते:

उपरोक्त SFG को किसी भी $n^{th}$ Fibonacci एलिमेंट तक पहुँचने के लिए आगे बढ़ाया जा सकता है। इसलिए, $n^{th}$ Fibonacci एलिमेंट की गणना करने के एल्गोरिथ्म को भी एक Signal Flow Graph के रूप में दर्शाया जा सकता है, जहाँ हम पहले दो एलिमेंट्स को input nodes के रूप में लेते हैं और $n^{th}$ एलिमेंट output node के रूप में प्रकट होता है। अन्य nodes mixed होते हैं।

उन पाठकों के लिए जो पहले से ही Fibonacci SFG से परिचित हैं, सरलता के लिए ग्राफ को बिना दिशाओं (directions) के इस प्रकार दर्शाया जा सकता है:

सामान्य तौर पर, जब हम उस एल्गोरिथ्म के संदर्भ (context) को जानते हैं जिसे SFG दर्शा रहा है, तो बिना तीरों (arrows) का उपयोग किए edges को चित्रित करना आम बात है।

अगले अध्याय में, हम देखेंगे कि NTT निष्पादित (perform) करने के लिए एल्गोरिथ्म लिखने हेतु Signal Flow Graphs का उपयोग कैसे किया जाता है।

यह लेख हमारी ZK Book में Number Theoretic Transform पर आधारित एक सीरीज़ का हिस्सा है।