{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T14:34:48Z","timestamp":1774967688376,"version":"3.50.1"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T00:00:00Z","timestamp":1564012800000},"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. Algorithms"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"\n We consider the fundamental problem of constructing fast circuits for the carry bit computation in binary addition. Up to a small additive constant, the carry bit computation reduces to computing an A\n nd<\/jats:sc>\n -O\n r<\/jats:sc>\n path, i.e., a formula of type\n t<\/jats:italic>\n 0<\/jats:sub>\n \u2227 (\n t<\/jats:italic>\n 1<\/jats:sub>\n \u2228 (\n t<\/jats:italic>\n 2<\/jats:sub>\n \u2227 (\u2026\n t<\/jats:italic>\n \n m<\/jats:italic>\n \u22121\n <\/jats:sub>\n ) \u2026) or\n t<\/jats:italic>\n 0<\/jats:sub>\n \u2228 (\n t<\/jats:italic>\n 1<\/jats:sub>\n \u2227 (\n t<\/jats:italic>\n 2<\/jats:sub>\n \u2228 (\u2026\n t<\/jats:italic>\n \n m<\/jats:italic>\n \u22121\n <\/jats:sub>\n ) \u2026). We present an algorithm that computes the fastest known Boolean circuit for an A\n nd<\/jats:sc>\n -O\n r<\/jats:sc>\n path\u00a0 with given arrival times\n a<\/jats:italic>\n (\n t<\/jats:italic>\n 0<\/jats:sub>\n ), \u2026,\n a<\/jats:italic>\n (\n t<\/jats:italic>\n \n m<\/jats:italic>\n \u22121\n <\/jats:sub>\n ) for the input signals. Our objective function is delay, a natural generalization of depth with respect to arrival times. The maximum delay of the circuit we compute is log\n 2<\/jats:sub>\n W<\/jats:italic>\n + log\n 2<\/jats:sub>\n log\n 2<\/jats:sub>\n m<\/jats:italic>\n + log\n 2<\/jats:sub>\n log\n 2<\/jats:sub>\n log\n 2<\/jats:sub>\n m<\/jats:italic>\n + 4.3, where\n W<\/jats:italic>\n := \u2211\n \n i<\/jats:italic>\n = 0\n <\/jats:sub>\n \n m<\/jats:italic>\n \u22121\n <\/jats:sup>\n 2\n \n a<\/jats:italic>\n (\n t<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n )\n <\/jats:sup>\n . Note that \u2308 log\n 2<\/jats:sub>\n W<\/jats:italic>\n \u2309 is a lower bound on the delay of any circuit depending on inputs\n t<\/jats:italic>\n 0<\/jats:sub>\n , \u2026,\n t<\/jats:italic>\n \n m<\/jats:italic>\n \u22121\n <\/jats:sub>\n with prescribed arrival times. Our method yields the fastest circuits for A\n nd<\/jats:sc>\n -O\n r<\/jats:sc>\n paths, carry bit computation, and adders in terms of delay known so far.\n <\/jats:p>","DOI":"10.1145\/3340321","type":"journal-article","created":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T12:34:33Z","timestamp":1564058073000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Faster Carry Bit Computation for Adder Circuits with Prescribed Arrival Times"],"prefix":"10.1145","volume":"15","author":[{"given":"Ulrich","family":"Brenner","sequence":"first","affiliation":[{"name":"Research Institute for Discrete Mathematics, University of Bonn, Bonn, Germany"}]},{"given":"Anna","family":"Hermann","sequence":"additional","affiliation":[{"name":"Research Institute for Discrete Mathematics, University of Bonn, Bonn, Germany"}]}],"member":"320","published-online":{"date-parts":[[2019,7,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1970.223027"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1675982"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264580"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264256"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1976.1674574"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1134\/S1990478909010086"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0067-x"},{"key":"e_1_2_1_8_1","first-page":"1098","article-title":"A method for the construction of minimum-redundancy codes","volume":"40","author":"Huffman David A.","year":"1952","journal-title":"Proceedings of the Institute of Radio Engineers"},{"key":"e_1_2_1_9_1","first-page":"105","article-title":"Asymptotic estimation of addition time of parallel adder","volume":"19","author":"Khrapchenko Valerii M.","year":"1970","journal-title":"Syst. Theory Res."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1134\/S1990478908020063"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1973.5009159"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322232"},{"key":"e_1_2_1_14_1","unstructured":"Dieter Rautenbach Christian Szegedy and J\u00fcrgen Werber. 2003. Asymptotically Optimal Boolean Circuits for Functions of the Form gn−1<\/sub>(gn−2<\/sub>(\u2026 g3<\/sub>(g2<\/sub>(g1<\/sub>(x1<\/sub> x2<\/sub>) x3<\/sub>) x4<\/sub>)\u2026 xn−1<\/sub>) xn<\/sub>) Given Input Arrival Times. Research Institute for Discrete Mathematics University of Bonn. Dieter Rautenbach Christian Szegedy and J\u00fcrgen Werber. 2003. Asymptotically Optimal Boolean Circuits for Functions of the Form g n −1<\/sub>( g n −2<\/sub>(\u2026 g 3<\/sub>( g 2<\/sub>( g 1<\/sub>( x 1<\/sub> x 2<\/sub>) x 3<\/sub>) x 4<\/sub>)\u2026 x n −1<\/sub>) x n <\/sub>) Given Input Arrival Times. Research Institute for Discrete Mathematics University of Bonn."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.06.006"},{"key":"e_1_2_1_16_1","volume-title":"Models of Computation","author":"Savage John E."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1960.5219822"},{"key":"e_1_2_1_18_1","volume-title":"Boolean Circuit Optimization. Master\u2019s thesis","author":"Spirkl Sophie"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1326073.1326184"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340321","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3340321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:32Z","timestamp":1750268972000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,25]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3340321"],"URL":"https:\/\/doi.org\/10.1145\/3340321","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,25]]},"assertion":[{"value":"2018-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}