FourierMotzkinGUI User Guide
Contents
1. Warning The elimination may take a long time depending on the complexity of the system Press CANCEL if you want to interrupt the elimination Press RESTART FME to restart it from the beginning Figure 5 Fourier Motzkin Elimination is running Step 6 See the result When FME finishes the initial and reduced systems are displayed Press EXPORT AS TEXT to save them in a text file SAVE session START Enter variables Enter Enter Choose Initial list of inequalities Ri ROl lt Ti Ri lt 12 R1 R01 R02 lt 13 Ri R02 lt I4 R2 RO2 lt IS R2 lt 16 R2 R01 R02 lt 17 R2 R01 lt I8 Reduced list of inequalities Ri 2 00 R2 2 00 R1 R2 Ri R2 Ri R2 Ri R2 R1 R2 lt lt lt lt lt lt lt I3 IS I8 Il 14 17 I4 I3 TE 12 16 I5 17 18 Export as text Figure 6 See the result The above figure directly gives the expected final system of inequalities 2 3 Ry 2Ro lt I X1U2 Y1 U1Q I X2 Y2 U1U2Q I X2U1 Y2 Q 2R Ra lt I X1 Vi UiU2Q I X1U2 Y lQ I X2U1 Y2 U2 Q R Ro lt I X1U2 Y Q I Xo Y2 U1U2Q Ry Ro lt I X103 Y1 U1Q I X21 Y2 U2Q Ry Ra lt I X1 Y U U2Q I X2U1 Y2 Q Ry lt I X1 Y lU2Q Ry lt I X2 Y2 UiQ 4 Others Functionnalities 4 1 Direct Access Buttons While moving forw2. and redistribute it with or without modifying it either commercially or noncommercially Secondarily this License preserves for the author and publisher a way to get credit for their work while not being considered responsible for modifications made by others This License is a kind of copyleft which means that derivative works of the document must them selves be free in the same sense It complements the GNU General Public License which is a copyleft license designed for free software We have designed this License in order to use it for manuals for free software because free software needs free documentation a free program should come with manuals providing the same freedoms that the software does But this License is not limited to software manuals it can be used for any textual work regardless of subject matter or whether it is published as a printed book We recommend this License principally for works whose purpose is instruction or reference 1 APPLICABILITY AND DEFINITIONS This License applies to any manual or other work in any medium that contains a notice placed by the copyright holder saying it can be distributed under the terms of this License Such a notice grants a world wide royalty free license unlimited in duration to use that work under the conditions stated herein The Document below refers to any such manual or work Any member of the public is a licensee and is addressed as you You accept the licens
3. distributed in the hope that it will be useful but WITHOUT ANY WAR RANTY without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICU LAR PURPOSE See the GNU General Public License for more details You should have received a copy of the GNU General Public License along with FourierMotzkinGUI If not see http www gnu org licenses 3 Basic Use The interface provides a step by step procedure as described below Screenshots are given for the Han Kobayashi inner bound 2 which provides achievable rates for a 2 user pair discrete memoryless interference channel X1 X2 gt Y1 Y2 In this setup senders 1 and 2 wish to send independent messages M and M resp with respective rates R4 and Ro to receivers 1 and 2 resp as depicted below In the coding scheme of 2 message M j 1 2 is divided in public and private parts with respective rates Ro and Rjj Sufficient conditions for the achievability of a tuple Roi Roz R11 R22 are given by the following system of inequalities 2 B R lt I X1 Yi Ui U2 Q R Ror lt I X1 Yi U2 Q R Roz lt I Xi U2 Y U1 Q Ri Roi Roz lt XI U2 Y1 Q Rog lt I X2 Ya U1 U2 Q Roo Rog lt I X2 Y2 U1 Q Rog Ror lt I X2 U1 Ya U2 Q Roo Ro2 Ror lt I Xo U1 Y2 Q for some auxiliary variables Q U and Us s t p qu uax xa p q p urr1 q p u2r2 q We would like to eliminate the a
4. of this License 2 VERBATIM COPYING You may copy and distribute the Document in any medium either commercially or noncommercially provided that this License the copyright notices and the license notice saying this License applies to the Document are reproduced in all copies and that you add no other conditions whatsoever to those of this License You may not use technical measures to obstruct or control the reading or further copying of the copies you make or distribute However you may accept compensation in exchange for copies If you distribute a large enough number of copies you must also follow the conditions in section 3 You may also lend copies under the same conditions stated above and you may publicly display copies 11 3 COPYING IN QUANTITY If you publish printed copies or copies in media that commonly have printed covers of the Doc ument numbering more than 100 and the Document s license notice requires Cover Texts you must enclose the copies in covers that carry clearly and legibly all these Cover Texts Front Cover Texts on the front cover and Back Cover Texts on the back cover Both covers must also clearly and legibly identify you as the publisher of these copies The front cover must present the full title with all words of the title equally prominent and visible You may add other material on the covers in addition Copying with changes limited to the covers as long as they preserve the title of the Docume
5. violation of this License then your license from a particular copyright holder is reinstated a provisionally unless and until the copyright holder explicitly and finally termi nates your license and b permanently if the copyright holder fails to notify you of the violation by some reasonable means prior to 60 days after the cessation Moreover your license from a particular copyright holder is reinstated permanently if the copyright holder notifies you of the violation by some reasonable means this is the first time you have received notice of violation of this License for any work from that copyright holder and you cure the violation prior to 30 days after your receipt of the notice Termination of your rights under this section does not terminate the licenses of parties who have received copies or rights from you under this License If your rights have been terminated and not permanently reinstated receipt of a copy of some or all of the same material does not give you any rights to use it 10 FUTURE REVISIONS OF THIS LICENSE The Free Software Foundation may publish new revised versions of the GNU Free Documentation License from time to time Such new versions will be similar in spirit to the present version but may differ in detail to address new problems or concerns See http www gnu org copyleft Each version of the License is given a distinguishing version number If the Document specifies that a particular numbered versi
6. FourierMotzkinGUI User Guide Joffrey Villard November 2011 Copyright C 2011 Joffrey Villard Permission is granted to copy distribute and or modify this document under the terms of the GNU Free Documentation License Version 1 3 or any later version published by the Free Software Foundation with no Invariant Sections no Front Cover Texts and no Back Cover Texts A copy of the license is included in the section entitled GNU Free Docu mentation License 1 Introduction FourierMotzkinGUI is a piece of software M code which provides a basic Graphical User Interface for Fourier Motzkin Elimination FME 1 with particular focus on applications to information theory This algorithm is useful to simplify achievable regions by eliminating meaningless quantities if possible but its application by hands can take hours The tool is able to work with symbolic quantities but does not perform any symbolic simplifications For instance it can manipulate formal quantities U A and I V AJU but will not write I U A I V AJU as I UV A Final results will thus contain some redundant inequalities which can be easily eliminated by standard manipulation 2 License FourierMotzkinGUl is free software you can redistribute it and or modify it under the terms of the GNU General Public License as published by the Free Software Foundation either version 3 of the License or at your option any later version FourierMotzkinGUI is
7. ally available and the machine generated HTML PostScript or PDF produced by some word processors for output purposes only The Title Page means for a printed book the title page itself plus such following pages as are needed to hold legibly the material this License requires to appear in the title page For works in formats which do not have any title page as such Title Page means the text near the most prominent appearance of the work s title preceding the beginning of the body of the text The publisher means any person or entity that distributes copies of the Document to the public A section Entitled XYZ means a named subunit of the Document whose title either is precisely XYZ or contains XYZ in parentheses following text that translates XYZ in another language Here XYZ stands for a specific section name mentioned below such as Acknowledgements Dedications Endorsements or History To Preserve the Title of such a section when you modify the Docu ment means that it remains a section Entitled XYZ according to this definition The Document may include Warranty Disclaimers next to the notice which states that this License applies to the Document These Warranty Disclaimers are considered to be included by reference in this License but only as regards disclaiming warranties any other implication that these Warranty Dis claimers may have is void and has no effect on the meaning
8. ard buttons indicating completed steps are turned on in the top menu They enable to move back to any previous step and make changes if needed FourierMotzkinGUI 1 0 Untitled Enter variables Figure 7 Direct access buttons 4 2 Save Load Sessions Press SAVE SESSION at any time to save the current session i e variables parameters inequalities depending on the completed steps in a MAT file At start press LOAD AN EXISTING SESSION then pick the corresponding MAT file The program will resume where it was when the session was saved References 1 Wikipedia org Fourier Motzkin elimination http en wikipedia org wiki 7 Oct 2010 2 T S Han and K Kobayashi A new achievable rate region for the interference channel JEEE Trans Inf Theory vol 27 no 1 pp 49 60 1981 3 A El Gamal and Y H Kim Lecture Notes on Network Information Theory 2010 Figure 8 Save a session Figure 9 Load a session A GNU Free Documentation License Version 1 3 3 November 2008 Copyright 2000 2001 2002 2007 2008 Free Software Foundation Inc lt http fsf org gt Everyone is permitted to copy and distribute verbatim copies of this license document but changing it is not allowed Preamble The purpose of this License is to make a manual textbook or other functional and useful document free in the sense of freedom to assure everyone the effective freedom to copy
9. e if you copy modify or distribute the work in a way requiring permission under copyright law A Modified Version of the Document means any work containing the Document or a portion of it either copied verbatim or with modifications and or translated into another language A Secondary Section is a named appendix or a front matter section of the Document that deals exclusively with the relationship of the publishers or authors of the Document to the Document s overall subject or to related matters and contains nothing that could fall directly within that overall subject Thus if the Document is in part a textbook of mathematics a Secondary Section may not explain any mathematics The relationship could be a matter of historical connection with the subject or with related matters or of legal commercial philosophical ethical or political position regarding them The Invariant Sections are certain Secondary Sections whose titles are designated as being those of Invariant Sections in the notice that says that the Document is released under this License If a section does not fit the above definition of Secondary then it is not allowed to be designated as Invariant The 10 Document may contain zero Invariant Sections If the Document does not identify any Invariant Sections then there are none The Cover Texts are certain short passages of text that are listed as Front Cover Texts or Back Cover Texts in the no
10. ed the old one The author s and publisher s of the Document do not by this License give permission to use their names for publicity for or to assert or imply endorsement of any Modified Version 13 5 COMBINING DOCUMENTS You may combine the Document vvith other documents released under this License under the terms defined in section 4 above for modified versions provided that you include in the combination all of the Invariant Sections of all of the original documents unmodified and list them all as Invariant Sections of your combined work in its license notice and that you preserve all their Warranty Disclaimers The combined work need only contain one copy of this License and multiple identical Invariant Sections may be replaced with a single copy If there are multiple Invariant Sections with the same name but different contents make the title of each such section unique by adding at the end of it in parentheses the name of the original author or publisher of that section if known or else a unique number Make the same adjustment to the section titles in the list of Invariant Sections in the license notice of the combined work In the combination you must combine any sections Entitled History in the various original docu ments forming one section Entitled History likewise combine any sections Entitled Acknowledge ments and any sections Entitled Dedications You must delete all sections Entitled Endorsemen
11. included in the Modified Version N Do not retitle any existing section to be Entitled Endorsements or to conflict in title with any Invariant Section O Preserve any Warranty Disclaimers If the Modified Version includes new front matter sections or appendices that qualify as Secondary Sections and contain no material copied from the Document you may at your option designate some or all of these sections as invariant To do this add their titles to the list of Invariant Sections in the Modified Version s license notice These titles must be distinct from any other section titles You may add a section Entitled Endorsements provided it contains nothing but endorsements of your Modified Version by various parties for example statements of peer review or that the text has been approved by an organization as the authoritative definition of a standard You may add a passage of up to five words as a Front Cover Text and a passage of up to 25 words as a Back Cover Text to the end of the list of Cover Texts in the Modified Version Only one passage of Front Cover Text and one of Back Cover Text may be added by or through arrangements made by any one entity If the Document already includes a cover text for the same cover previously added by you or by arrangement made by the same entity you are acting on behalf of you may not add another but you may replace the old one on explicit permission from the previous publisher that add
12. name expression of all involved parameters in the editable field Press OK between each one The List OF PARAMETERS is automatically updated Parameters are understood as non negative real num bers e g mutual information entropy You can also EDIT or DELETE a parameter already in the list or CLEAR the whole list using the appropriate button Press ENTER INEQUALITIES when finished FourierMotzkinGUI 1 0 Untitled save session _sTart__ gt gt Enter variables gt gt Enter parameters gt gt Enter the name of a non negative parameter List of variables List of parameters 21 I2 13 I4 I5 v Edit selected Delete selected Clear all I Enter inequalities Figure 2 Enter parameters The reasons why the parameters are not included in the variables are the following e Parameters can not be simplified by FME they are constants e We usually write inequalities some variables lt some parameters e Knowing that they are non negative allows more powerfull reduction after application of FME Step 3 Enter inequalities Enter the coefficients real numbers of variables parameters for each inequality of the system in the editable fields Press OK between each inequality The List OF INEQUALITIES is automatically updated You can also EDIT or DELETE an inequality already in the list or CLEAR the whole list using the appr
13. nt s license notice H Include an unaltered copy of this License I Preserve the section Entitled History Preserve its Title and add to it an item stating at least the title year new authors and publisher of the Modified Version as given on the Title Page If there is no section Entitled History in the Document create one stating the title year authors and publisher of the Document as given on its Title Page then add an item describing the Modified Version as stated in the previous sentence J Preserve the network location if any given in the Document for public access to a Transparent copy of the Document and likewise the network locations given in the Document for previous versions it was based on These may be placed in the History section You may omit a network location for a work that was published at least four years before the Document itself or if the original publisher of the version it refers to gives permission K For any section Entitled Acknowledgements or Dedications Preserve the Title of the section and preserve in the section all the substance and tone of each of the contributor acknowledgements and or dedications given therein L Preserve all the Invariant Sections of the Document unaltered in their text and in their titles Section numbers or the equivalent are not considered part of the section titles M Delete any section Entitled Endorsements Such a section may not be
14. nt and satisfy these conditions can be treated as verbatim copying in other respects If the required texts for either cover are too voluminous to fit legibly you should put the first ones listed as many as fit reasonably on the actual cover and continue the rest onto adjacent pages If you publish or distribute Opaque copies of the Document numbering more than 100 you must either include a machine readable Transparent copy along with each Opaque copy or state in or with each Opaque copy a computer network location from which the general network using public has access to download using public standard network protocols a complete Transparent copy of the Document free of added material If you use the latter option you must take reasonably prudent steps when you begin distribution of Opaque copies in quantity to ensure that this Transparent copy will remain thus accessible at the stated location until at least one year after the last time you distribute an Opaque copy directly or through your agents or retailers of that edition to the public It is requested but not required that you contact the authors of the Document well before redistribut ing any large number of copies to give them a chance to provide you with an updated version of the Document 4 MODIFICATIONS You may copy and distribute a Modified Version of the Document under the conditions of sections 2 and 3 above provided that you release the Modified Version under preci
15. on of this License or any later version applies to it you have the option of following the terms and conditions either of that specified version or of any later version that has been published not as a draft by the Free Software Foundation If the Document does not specify a version number of this License you may choose any version ever published not as a draft by the Free Software Foundation If the Document specifies that a proxy can decide which future versions of this License can be used that proxy s public statement of acceptance of a version permanently authorizes you to choose that version for the Document 11 RELICENSING Massive Multiauthor Collaboration Site or MMC Site means any World Wide Web server that publishes copyrightable works and also provides prominent facilities for anybody to edit those works A public wiki that anybody can edit is an example of such a server A Massive Multiauthor Collaboration or MMC contained in the site means any set of copyrightable works thus published on the MMC site 15 CC BY SA means the Creative Commons Attribution Share Alike 3 0 license published by Cre ative Commons Corporation a not for profit corporation with a principal place of business in San Fran cisco California as well as future copyleft versions of that license published by that same organization Incorporate means to publish or republish a Document in whole or in part as part of anothe
16. opriate button Press CHOOSE REMAINING VARIABLES when finished Step 4 Choose remaining variables Select the meaningful variables that FME should not eliminate i e those which are needed to describe the region Press RUN FOURIER MOTZKIN when finished save session __sTart__ gt gt Enter variables gt gt enter parameters gt gt Enter inequaities gt gt abies gt gt gt gt Enter an inequality R1 1 R2 1 ror 1 R02 lt I 12 813 I4 415 I6 1 17 18 OK List of inequalities Ri RO1 lt Ii a R1 lt I2 R1 R01 R02 lt 13 R1 R02 lt I4 R2 R02 lt IS R2 lt I6 I v Edit selected Delete selected Clear all Choose remaining variables Figure 3 Enter inequalities FourierMotzkinGUI 1 0 Untitled save session __sTart__ gt gt enter variables gt gt Enter parameters gt gt Enter inequsities gt gt choose remaining variables gt gt Choose the remaining variables 7 w Run Fourier Motzkin Figure 4 Choose remaining variables Step 5 Fourier Motzkin Elimination is running While FME is running some messages are displayed e g the variable currently being eliminated or the total number of remaining inequalities
17. or the electronic equivalent of covers if the Document is in electronic form Otherwise they must appear on printed covers that bracket the whole aggregate 8 TRANSLATION Translation is considered a kind of modification so you may distribute translations of the Document under the terms of section 4 Replacing Invariant Sections with translations requires special permission from their copyright holders but you may include translations of some or all Invariant Sections in addi tion to the original versions of these Invariant Sections You may include a translation of this License and all the license notices in the Document and any Warranty Disclaimers provided that you also include 14 the original English version of this License and the original versions of those notices and disclaimers In case of a disagreement between the translation and the original version of this License or a notice or disclaimer the original version will prevail If a section in the Document is Entitled Acknowledgements Dedications or History the re quirement section 4 to Preserve its Title section 1 will typically require changing the actual title 9 TERMINATION You may not copy modify sublicense or distribute the Document except as expressly provided under this License Any attempt otherwise to copy modify sublicense or distribute it is void and will automatically terminate your rights under this License However if you cease all
18. r Document An MMC is eligible for relicensing if it is licensed under this License and if all works that were first published under this License somewhere other than this MMC and subsequently incorporated in whole or in part into the MMC 1 had no cover texts or invariant sections and 2 were thus incorporated prior to November 1 2008 The operator of an MMC Site may republish an MMC contained in the site under CC BY SA on the same site at any time before August 1 2009 provided the MMC is eligible for relicensing ADDENDUM How to use this License for your documents To use this License in a document you have written include a copy of the License in the document and put the following copyright and license notices just after the title page Copyright YEAR YOUR NAME Permission is granted to copy distribute and or modify this document under the terms of the GNU Free Documentation License Version 1 3 or any later version published by the Free Software Foundation with no Invariant Sections no Front Cover Texts and no Back Cover Texts A copy of the license is included in the section entitled GNU Free Documentation License If you have Invariant Sections Front Cover Texts and Back Cover Texts replace the with Texts line with this with the Invariant Sections being LIST THEIR TITLES with the Front Cover Texts being LIST and with the Back Cover Texts being LIST If you have Invariant Sections without Co
19. sely this License with the Modified Version filling the role of the Document thus licensing distribution and modification of the Modified Version to whoever possesses a copy of it In addition you must do these things in the Modified Version A Use in the Title Page and on the covers if any a title distinct from that of the Document and from those of previous versions which should if there were any be listed in the History section of the Document You may use the same title as a previous version if the original publisher of that version gives permission B List on the Title Page as authors one or more persons or entities responsible for authorship of the modifications in the Modified Version together with at least five of the principal authors of the Document all of its principal authors if it has fewer than five unless they release you from this requirement C State on the Title page the name of the publisher of the Modified Version as the publisher D Preserve all the copyright notices of the Document E Add an appropriate copyright notice for your modifications adjacent to the other copyright notices 12 F Include immediately after the copyright notices a license notice giving the public permission to use the Modified Version under the terms of this License in the form shown in the Addendum below G Preserve in that license notice the full lists of Invariant Sections and required Cover Texts given in the Docume
20. tice that says that the Document is released under this License A Front Cover Text may be at most 5 words and a Back Cover Text may be at most 25 words A Transparent copy of the Document means a machine readable copy represented in a format whose specification is available to the general public that is suitable for revising the document straight forwardly with generic text editors or for images composed of pixels generic paint programs or for drawings some widely available drawing editor and that is suitable for input to text formatters or for automatic translation to a variety of formats suitable for input to text formatters A copy made in an otherwise Transparent file format whose markup or absence of markup has been arranged to thwart or discourage subsequent modification by readers is not Transparent An image format is not Transparent if used for any substantial amount of text A copy that is not Transparent is called Opaque Examples of suitable formats for Transparent copies include plain ASCII without markup Tex info input format LaTeX input format SGML or XML using a publicly available DTD and standard conforming simple HTML PostScript or PDF designed for human modification Examples of transparent image formats include PNG XCF and JPG Opaque formats include proprietary formats that can be read and edited only by proprietary word processors SGML or XML for which the DTD and or processing tools are not gener
21. ts 6 COLLECTIONS OF DOCUMENTS You may make a collection consisting of the Document and other documents released under this License and replace the individual copies of this License in the various documents with a single copy that is included in the collection provided that you follow the rules of this License for verbatim copying of each of the documents in all other respects You may extract a single document from such a collection and distribute it individually under this License provided you insert a copy of this License into the extracted document and follow this License in all other respects regarding verbatim copying of that document 7 AGGREGATION WITH INDEPENDENT WORKS A compilation of the Document or its derivatives with other separate and independent documents or works in or on a volume of a storage or distribution medium is called an aggregate if the copyright resulting from the compilation is not used to limit the legal rights of the compilation s users beyond what the individual works permit When the Document is included in an aggregate this License does not apply to the other works in the aggregate which are not themselves derivative works of the Document If the Cover Text requirement of section 3 is applicable to these copies of the Document then if the Document is less than one half of the entire aggregate the Document s Cover Texts may be placed on covers that bracket the Document within the aggregate
22. uxiliary rates and obtain a new system that only involves Ry Ro Ry and Ro Ro2 Roo Fourier Motzkin elimination is appropriate here see also its application by hands to the same system in 3 Appendix D X Y P M Sender 1 Receiver 1 gt M DM IC Mz Sender 2 a PE ye Receiver 2 Ms Interference channel Step 0 START At start it is possible to LOAD AN EXISTING SESSION see Section 4 2 below or CREATE A NEW ONE In the next paragraphs we present the whole procedure i e create a new session Step 1 Enter variables Enter the name of all involved variables in the editable field Press OK between each one The List OF VARIABLES is automatically updated Variables are understood as real numbers which describe some regions of R e g rates Some of them are meaningful others will be eliminated using FME You can also EDIT or DELETE a variable already in the list or CLEAR the whole list using the appro priate button Press ENTER PARAMETERS when finished FourierMotzkinGUI 1 0 Untitled save session __start__ gt gt Enter variables gt gt Enter the name of a variable List of variables List of parameters Edit selected Delete selected Clear all Enter parameters Figure 1 Enter variables Step 2 Enter parameters Enter the
23. ver Texts or some other combination of the three merge those two alternatives to suit the situation If your document contains nontrivial examples of program code we recommend releasing these examples in parallel under your choice of free software license such as the GNU General Public License to permit their use in free software 16
Download Pdf Manuals
Related Search