Understanding Feedback Composition in Systems Analysis
Explore the concept of feedback composition in systems analysis, where outputs from state machines are fed back as inputs. Learn about fixed points, well-formed compositions, and the intricacies of creating effective feedback loops in synchronous models.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSE314: SYSTEMS ANALYSIS Lecture 05: Feedback State Machines Dr. Ahmed Mahmoud, --/10/2020
Feedback Composition In simple feedback systems, an output from a state machine is fed back as an input to the same state machine. In more complicated feedback systems, several state machines might be connected in a loop. Feedback is a subtle form of composition in the synchronous model. For synchronous composition models, in a reaction, the output symbol of a state machine is simultaneous with the input symbol. The output symbol of a machine in feedback composition depends on an input symbol that depends on its own output symbol! CSE314: SYSTEMS ANALYSIS --/10/2020 2
Fixed Point (1) Fixed point is to find ? for a function ? such that ? = ? ? . It is analogous to feedback because the output ?(?) of ? is equal to its input ?, and vice versa. A more complicated problem, involving two equations, is to find ? and ?, so that: The analogous feedback composition has two state machines in feedback as: CSE314: SYSTEMS ANALYSIS --/10/2020 3
Fixed Point (2) A fixed-point equation may have no fixed point, a unique fixed point, or multiple fixed points. For a function: ? ? = 1 + ?2 has no fixed point in the reals. ? ? = 1 ? has unique fixed point. ? ? = ?2 has two fixed points. Ill-formed: a feedback composition with no fixed point in some reachable state is a defective design. (Or have more than one fixed point). Well-formed: A feedback composition with a unique non-stuttering fixed point in all reachable states is. Fortunately, it is easy to construct well-formed feedback compositions, and they prove surprisingly useful. CSE314: SYSTEMS ANALYSIS --/10/2020 4
Ill-formed vs. Well-formed CSE314: SYSTEMS ANALYSIS --/10/2020 5
Feedback Composition With No Inputs (1) The alphabet for inputs and outputs are: For feedback back connection to be possible: The challenge is to find to satisfy: CSE314: SYSTEMS ANALYSIS --/10/2020 6
Feedback Composition With No Inputs (2) We must find ?(?) such that: This is a fixed point problem. A trivial solution is to stutter: Well-formed feedback composition if for every reachable ? ? ???????, there is a unique non-stuttering output symbol ?(?) that solves the fixed point; otherwise, the composition is ill-formed. CSE314: SYSTEMS ANALYSIS --/10/2020 7
Well-Formed Feedback Composition CSE314: SYSTEMS ANALYSIS --/10/2020 8
State-Determined Output A state machine has a state-determined output if in every reachable state ? ? ???????, there is a unique output symbol ? ? = ?. CSE314: SYSTEMS ANALYSIS --/10/2020 9
Example on State-Determined Output A is state-determined output, B is NOT. The feedback composition is well- formed: It is not necessary for machine A to be state-determined output to have a well-formed feedback composition. CSE314: SYSTEMS ANALYSIS --/10/2020 10
Feedback Composition With Inputs (1) The output function has two equations: The composition of is well-formed if for every reachable state ? ? ??????? and for every external input symbol ?1 ? ???????1, there is a unique non-stuttering output symbol ?2 ? ????????2 that solves previous equations. CSE314: SYSTEMS ANALYSIS --/10/2020 11
Feedback Composition With Inputs (2) is the unique solution for output equations. CSE314: SYSTEMS ANALYSIS --/10/2020 12
Example Feedback Composition With Inputs A has infinite input and output alphabets and infinitely many states. The update function is: The feedback connects ? to ?2, thus: CSE314: SYSTEMS ANALYSIS --/10/2020 13
Constructive Procedure for Feedback Composition CSE314: SYSTEMS ANALYSIS --/10/2020 14
Challenges of Constructive Procedure for Feedback Composition This procedure can be applied in general to any composition of state machines. If the procedure can be applied successfully (nothing remains unknown) for all reachable states of the composition, then the composition is well-formed. The sort of reasoning in this more complicated example is difficult and error-prone for even moderate compositions of state machines. It is best automated. Compilers for synchronous languages do exactly this. Successfully compiling a program involves proving that feedback loops are well-formed. If a feedback composition has one or more machines with state-determined output, then finding a unique fixed point is easy. Without such state-determined output, we can apply the procedure in the previous section. Unfortunately, if the procedure fails, we cannot conclude that the composition is ill-formed. CSE314: SYSTEMS ANALYSIS --/10/2020 15
