{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:29:25Z","timestamp":1774369765492,"version":"3.50.1"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2006,4,1]],"date-time":"2006-04-01T00:00:00Z","timestamp":1143849600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2006,4]]},"abstract":"<jats:p>\n            A parallel prefix circuit has\n            <jats:italic>n<\/jats:italic>\n            inputs\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ,\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            , \u2026,\n            <jats:italic>\n              x\n              <jats:sub>n<\/jats:sub>\n            <\/jats:italic>\n            , and computes the\n            <jats:italic>n<\/jats:italic>\n            outputs\n            <jats:italic>\n              y\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            =\n            <jats:italic>\n              x\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            \u2022\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n              \u22121\n            <\/jats:sub>\n            \u2022\u2026\u2022\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , 1 \u2264\n            <jats:italic>i<\/jats:italic>\n            \u2264\n            <jats:italic>n<\/jats:italic>\n            , in parallel, where \u2022 is an arbitrary binary associative operator. Snir proved that the depth\n            <jats:italic>t<\/jats:italic>\n            and size\n            <jats:italic>s<\/jats:italic>\n            of any parallel prefix circuit satisfy the inequality\n            <jats:italic>t<\/jats:italic>\n            +\n            <jats:italic>s<\/jats:italic>\n            \u22652\n            <jats:italic>n<\/jats:italic>\n            \u22122. Hence, a parallel prefix circuit is said to be of zero-deficiency if equality holds. In this article, we provide a different proof for Snir's theorem by capturing the structural information of zero-deficiency prefix circuits. Following our proof, we propose a new kind of zero-deficiency prefix circuit\n            <jats:italic>Z<\/jats:italic>\n            (\n            <jats:italic>d<\/jats:italic>\n            ) by constructing a prefix circuit as wide as possible for a given depth\n            <jats:italic>d<\/jats:italic>\n            . It is proved that the\n            <jats:italic>Z<\/jats:italic>\n            (\n            <jats:italic>d<\/jats:italic>\n            ) circuit has the minimal depth among all possible zero-deficiency prefix circuits.\n          <\/jats:p>","DOI":"10.1145\/1142155.1142162","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"387-409","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["On the construction of zero-deficiency parallel prefix circuits with minimum depth"],"prefix":"10.1145","volume":"11","author":[{"given":"Haikun","family":"Zhu","sequence":"first","affiliation":[{"name":"University of California, San Diego, La Jolla, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chung-Kuan","family":"Cheng","sequence":"additional","affiliation":[{"name":"University of California, San Diego, La Jolla, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronald","family":"Graham","sequence":"additional","affiliation":[{"name":"University of California, San Diego, La Jolla, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676655"},{"key":"e_1_2_1_2_1","first-page":"3","article-title":"A regular layout for parallel adders","volume":"31","author":"Brent R. P.","year":"1982","journal-title":"IEEE Trans. Comput."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808738"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322232"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195088496.001.0001","volume-title":"Parallel Computing: Using the Prefix Problem","author":"Lakshmivarahan S.","year":"1994"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 1987 International Conference on Parallel Processing. 58--65","author":"Lakshmivarahan S."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00058-7"},{"key":"e_1_2_1_8_1","first-page":"3","article-title":"Z4: A new depth-size optimal parallel prefix circuit with small depth","volume":"11","author":"Lin Y. C.","year":"2003","journal-title":"Neural, Parall. Sci. Comput."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2003.09.004"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022084814175"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008147229964"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1960.5219822"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90003-9"},{"key":"e_1_2_1_14_1","unstructured":"Zimmermann R. Java applet for adder synthesis. In http:\/\/www.iis.ee.ethz.ch\/zimmi\/applets\/prefix.html.  Zimmermann R. Java applet for adder synthesis. In http:\/\/www.iis.ee.ethz.ch\/zimmi\/applets\/prefix.html."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the International Workshop on Logic and Architecture Synthesis. 123--132","author":"Zimmermann R.","year":"1996"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1142155.1142162","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1142155.1142162","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:11Z","timestamp":1750259171000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1142155.1142162"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,4]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,4]]}},"alternative-id":["10.1145\/1142155.1142162"],"URL":"https:\/\/doi.org\/10.1145\/1142155.1142162","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,4]]},"assertion":[{"value":"2006-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}