Lupanov decoding networks

This paper presents systematic synthesis procedures for Lupanov decoding networks. Decoding networks find applications in computer memories for the selection of a particular item of data addressed by a binary code, in counter circuits, in character-by-character code conversion circuits, in the synthesis of switching functions and also in the theoretical derivations of complexity bounds for arbitrary switching networks. In particular, a complete decoding network of n input variables provides a distinct output for each of the 2n possible combinations of the variables. These networks have been studied extensively, both in terms of relay contact realizations1,2 and in terms of gate-type element realizations3. Moore4 has shown that for disjunctive contact networks, hence for networks of branch-type elements, the familiar transfer trees using CM = 2(2n-1) contacts are the only possible minimal n variable decoding networks. In applications where disjunctivity of the outputs is not required, Lupanov5 has shown that the required number of contacts can be reduced considerably (by a factor of 2 as n grows arbitrarily large). Short6 has examined specific design procedures using Lupanov´s approach. The main idea is based on the design of a r-variable partial decoder, where r = 2k, k = 2,3,... whose 2r/r outputs consist of mutually disjoint groups of r vertices, collectively exhausting all the vertices of the r-cube such that any vertex is ? distinguished from the rest of the vertices in the group by the value of a single variable. The problem that has been posed7 and solved in this paper is the following: can we take r ≠ 2k for the partial decoder and find Lupanov trees whose costs are smaller than those obtained using r = 2k? We shall prove that this is possible and present systematic procedures for the design of Lupanov trees. The Lupanov trees obtained by our method have the best minimal costs known so far for all values of n. As an example, we have designed a 5-var- iable decoder which uses only 58 contacts compared to 60 contacts used by Lupanov.