{"id":146,"date":"2016-10-05T10:58:10","date_gmt":"2016-10-05T09:58:10","guid":{"rendered":"https:\/\/blogs.ncl.ac.uk\/jrbeaumont\/?p=146"},"modified":"2016-10-05T10:58:10","modified_gmt":"2016-10-05T09:58:10","slug":"concepts-vi-or-causality-part-1","status":"publish","type":"post","link":"https:\/\/blogs.ncl.ac.uk\/jrbeaumont\/2016\/10\/05\/concepts-vi-or-causality-part-1\/","title":{"rendered":"Concepts VI: OR-causality – Part 1"},"content":{"rendered":"

OR-causality is an interesting part of specification of circuits, specifically when using Signal Transition Graphs (STGs). We have recently released a translation tool for\u00a0Concepts (<\/em>available from\u00a0https:\/\/github.com\/tuura\/concepts<\/a>), which will take a set of concepts, and produce an STG specification for this. This includes both standard AND-causality, and OR-causality. OR-causality poses a challenge, as with STGs, and in this post we aim to discuss this.<\/p>\n

This will be a\u00a02 part series, with several examples to help explain OR-causality in this post, part 1, and an algorithm in part 2 to translate OR-causality concepts to STGs.<\/p>\n

OR-causality, an introduction
\n<\/span><\/strong><\/p>\n

For this, let’s use four\u00a0simple examples. Here, we will assume initial states for all signals as 0.<\/p>\n

    \n
  1. OR-Gate<\/span><\/li>\n<\/ol>\n

    A standard gate used in many applications, an OR-gate, and the associated causality, \u00a0is important and a good example to use to display OR-causality.<\/p>\n

    In\u00a0concepts, an OR-gate is defined as follows:<\/p>\n

    orGate a b c =<\/strong>\u00a0[a+, b+] ~|~> c+ \u22c4 a- \u21dd c-\u00a0\u22c4 b-\u00a0\u21dd c-<\/strong><\/p>\n

    There are some operators to discuss here:<\/p>\n

    [a+ , b+] – This is how signal transitions are listed.
    \n~|~> – This shows an OR-Causalilty relationship<\/p>\n

    In words, this is a composition of three concepts. First, either<\/em>\u00a0a+<\/strong> or<\/em>\u00a0b+\u00a0<\/strong>cause\u00a0c+<\/strong>. Then,\u00a0a-<\/strong> causes\u00a0c-<\/strong>, and\u00a0b-\u00a0<\/strong>causes\u00a0c-<\/strong>.<\/p>\n

    This will mean that, when a+,<\/strong>\u00a0\u00a0b+<\/strong>\u00a0or both of these\u00a0<\/strong>occur, c+<\/strong> can occur. But, for\u00a0c-\u00a0<\/strong>to occur,\u00a0a-\u00a0<\/strong>and\u00a0b-<\/strong> must have occurred.<\/p>\n

    \"OR_gate\"<\/a><\/p>\n

    This is the STG produced from translating the OR-gate concept. This looks like any other STG we have shown on this blog, however notice that there are two\u00a0c+<\/strong> transitions. This is how OR-causality is displayed in STGs. When\u00a0a+\u00a0<\/strong>occurs, one of the\u00a0c+<\/strong> transitions can occur. When\u00a0b+\u00a0<\/strong>occurs, the other\u00a0c+<\/strong> transition can occur. If both\u00a0a+<\/strong> and\u00a0b+<\/strong> have occurred, then either of the\u00a0c+\u00a0<\/strong>transitions can occur. However, both\u00a0a-\u00a0<\/strong>and\u00a0b-<\/strong> can occur, then and only then can\u00a0c-<\/strong> occur.<\/p>\n

    Notice, that for the\u00a0c+<\/strong> transition, there is OR-causality with a+<\/strong>\u00a0or\u00a0b+<\/strong>, but for the\u00a0c-<\/strong> transition, there is AND-causality with\u00a0a-<\/strong> and\u00a0b-<\/strong>.<\/p>\n

    2. OR-Gate with a single AND-causality<\/span><\/p>\n

    This is an OR-gate with inputs a<\/strong>\u00a0and\u00a0b<\/strong>, and output c<\/strong>, with another input signal\u00a0d<\/strong>.\u00a0d<\/strong> will form a buffer with\u00a0c, including some AND-causality as well. This way we can show how AND- and OR-Causality interact.\u00a0<\/strong>In concepts this is:<\/p>\n

    circuit \u00a0= orGate a b c\u00a0\u22c4 buffer d c<\/strong><\/p>\n

    And, expanded into signal-level concepts, this is:<\/p>\n

    circuit =\u00a0[a+, b+] ~|~> c+ \u22c4 a- \u21dd c-\u00a0\u22c4 b-\u00a0\u21dd c-\u00a0\u22c4 d+\u00a0\u21dd c+\u00a0\u22c4 d- \u21dd c-<\/strong><\/p>\n

    In words, for\u00a0c+\u00a0<\/strong>to occur,\u00a0d+<\/strong>\u00a0must\u00a0occur, and<\/em>\u00a0either\u00a0<\/em>b+\u00a0<\/strong>or<\/em>\u00a0c+<\/strong>. For\u00a0c-\u00a0<\/strong>to occur, all of a-<\/strong>,\u00a0b-<\/strong> and\u00a0d-<\/strong> must occur.<\/p>\n

    So, as a thought experiment, if\u00a0a+\u00a0<\/strong>and\u00a0b+<\/strong> have occurred, no\u00a0c+\u00a0<\/strong>transition can occur without\u00a0d+<\/strong>\u00a0having occurred.<\/p>\n

    The STG after translating the above concept is:\"OR_gate_1_AND_causality\"<\/a><\/p>\n

    Notice that this looks similar to the previous image, but with an extra consistency loop for the signal\u00a0d<\/strong>. However, notice that\u00a0d1<\/strong>, the place showing when\u00a0d+<\/strong> has occured, is connected to\u00a0both\u00a0<\/strong><\/em>c+<\/strong> transitions. And\u00a0d0<\/strong> is connected to\u00a0c-<\/strong>. This will therefore mean that, regardless of which of a+ <\/b>or\u00a0b+<\/strong>\u00a0have occured,\u00a0c+\u00a0<\/strong>cannot occur without\u00a0d+<\/strong> occuring.<\/p>\n

    3.\u00a0AND-Gate<\/span><\/p>\n

    Another standard gate. In this case, when thinking of it in terms of causality, it is the opposite of the OR-gate. i.e. For the\u00a0c+<\/strong> transition, there is AND-causality with both the\u00a0a+\u00a0<\/strong>and\u00a0b+\u00a0<\/strong>transition. Yet, with the\u00a0c-<\/strong> transition, there is OR-causality between the\u00a0a-\u00a0<\/strong>and\u00a0b-<\/strong> transitions.<\/p>\n

    The concepts for this is:<\/p>\n

    andGate a b c \u00a0=\u00a0a+ \u21dd c+ \u22c4 b+ \u21dd c+\u00a0\u22c4\u00a0[a-, b-] ~|~> c-<\/strong><\/p>\n

    This can be described in words as in the previous paragraph.<\/p>\n

    Let’s translate this to an STG.\"AND-Gate\"<\/a><\/p>\n

    Notice that this time, there are two c-<\/strong> transitions, as this transition is the OR-causality in an AND-gate. Notice the similarities between this and the OR-gate STG, just a sort-of mirror image.<\/p>\n

    4. AND-Gate and OR-Gate<\/span><\/p>\n

    For this, signals\u00a0a<\/strong> and\u00a0b\u00a0<\/strong>are the inputs to an OR-gate, and signals\u00a0d<\/strong> and\u00a0e<\/strong> are the inputs to an AND-gate. The outputs for both of these gates are\u00a0c<\/strong>. Synthesizing this would not simply produce an AND and OR gate, but for this example, it shows how the AND and OR causality can interact in and interesting way.<\/p>\n

    This in concepts is:<\/p>\n

    circuit = orGate a b c <> andGate d e c<\/strong><\/p>\n

    If we expand this:<\/p>\n

    circut = [a+, b+] ~|~> c+ \u22c4 a- \u21dd c- \u22c4 b- \u21dd c-\u00a0\u22c4
    \n<\/strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 d+\u00a0\u21dd c+\u00a0\u22c4 e+ \u21dd c+ \u22c4 [d-, e-]\u00a0\u21dd c-<\/strong><\/p>\n

    In words, this means that for\u00a0c+<\/strong> to occur, either<\/em>\u00a0a+\u00a0<\/strong>or<\/em>\u00a0b+<\/strong>,\u00a0and<\/em> both\u00a0<\/em>d+\u00a0<\/strong>and\u00a0c+\u00a0<\/strong>must have occured. For\u00a0c-<\/strong> to occur,\u00a0both\u00a0<\/em>a-<\/strong> and\u00a0<\/em>b-<\/strong>, and\u00a0either<\/em>\u00a0d-\u00a0<\/strong>or\u00a0<\/em>e-<\/strong> must have occured.<\/p>\n

    This is slightly more confusing than the previous examples, and the resulting STG produced by translating this concept is interesting:<\/p>\n

    \"AND-OR-Gate\"<\/a><\/p>\n

    It does look a little confusing, but notice there are two of both\u00a0c+<\/strong> and\u00a0c-<\/strong> transitions. Their interactions with\u00a0the other signals determine which of these are able to transition. Testing this would prove that the concept description above works.<\/p>\n

    Finally<\/span><\/strong><\/p>\n

    There is little reuse here. The concepts above feature some reuse of previously discussed concepts, but due to the inclusion of OR-causality, we cannot use any previously included gate- or protocol-concept as they do not feature any OR-causality.<\/p>\n

    So in this post, we have discussed OR-causality, and some uses of it. Specifically, I have aimed to show how it works on it’s own, and in conjunction with AND-causality.<\/p>\n

    Part 2 of this post will include an algorithm, as we have previously discussed how concepts are translated\u00a0to STGs, but this algorithm will explain how OR-causality is translated, as this is quite specific.<\/p>\n","protected":false},"excerpt":{"rendered":"

    OR-causality is an interesting part of specification of circuits, specifically when using Signal Transition Graphs (STGs). We have recently released a translation tool for\u00a0Concepts (available from\u00a0https:\/\/github.com\/tuura\/concepts), which will take a set of concepts, and produce an STG specification for this. This includes both standard AND-causality, and OR-causality. OR-causality poses a challenge, as with STGs, and … Continue reading Concepts VI: OR-causality – Part 1<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":6010,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-146","post","type-post","status-publish","format-standard","hentry","category-uncategorised"],"_links":{"self":[{"href":"https:\/\/blogs.ncl.ac.uk\/jrbeaumont\/wp-json\/wp\/v2\/posts\/146","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ncl.ac.uk\/jrbeaumont\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ncl.ac.uk\/jrbeaumont\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ncl.ac.uk\/jrbeaumont\/wp-json\/wp\/v2\/users\/6010"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ncl.ac.uk\/jrbeaumont\/wp-json\/wp\/v2\/comments?post=146"}],"version-history":[{"count":8,"href":"https:\/\/blogs.ncl.ac.uk\/jrbeaumont\/wp-json\/wp\/v2\/posts\/146\/revisions"}],"predecessor-version":[{"id":159,"href":"https:\/\/blogs.ncl.ac.uk\/jrbeaumont\/wp-json\/wp\/v2\/posts\/146\/revisions\/159"}],"wp:attachment":[{"href":"https:\/\/blogs.ncl.ac.uk\/jrbeaumont\/wp-json\/wp\/v2\/media?parent=146"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ncl.ac.uk\/jrbeaumont\/wp-json\/wp\/v2\/categories?post=146"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ncl.ac.uk\/jrbeaumont\/wp-json\/wp\/v2\/tags?post=146"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}