M out of n code checker circuit

Abstract

An N bit input word is partitioned into parts, preferably N/3 parts of 3 bits each. Each part is counted in parallel for the number of binary ones contained therein in first stage parallel code generators, preferably in N/3 parallel berger code generators each producing on 2 binary encoded signal lines that number of binary ones as are contained within 3 input signal lines. The binary encoded signal lines from the parallel code generators are added in a second stage binary tree of adders, such adders as are used in conjunction with first stage berger code generators progressing from N/6 adders of 2 bits width at level 1 to 1 adder of ln.sub.2 (N/3)+1 bits width at level ln.sub.2 (N/3). The final adder produces (X+1) binary encoded signals representing the number of binary ones contained within the input word, 2.sup.X+1.gtoreq. N. A final comparator stage based on exclusive OR gates and an OR gate(s) compares the X+1 signals representing the actual bit count with an equal number of binary encoded signals representing the then desired number M, M.ltoreq.N, and produces an error signal if the number of binary ones detected is not equal to M. A preferred embodiment implementation of the berger code generator circuits utilizes exclusive OR logical elements based on the CMOS technology transfer gate structure.