Academia.eduAcademia.edu

Outline

Compact fixed-threshold and two-vector Hamming comparators

2003, Electronics Letters

https://doi.org/10.1049/EL:20031054

Abstract

Compact circuits for the implementation of digital CMOS Hamming comparators are presented. One circuit compares the Hamming weight of an n-bit input vector to a fixed threshold, while the other compares the Hamming weights of two independent vectors (of equal or different lengths). Such comparators find applications in median=rank rank filters, vector quantisers, and digital neural networks.

Compact fixed-threshold and two-vector Hamming comparators recently reported implementations [3, 4], and, contrary to those, allows m 6¼ n as well. V.A. Pedroni Compact circuits for the implementation of digital CMOS Hamming comparators are presented. One circuit compares the Hamming weight of an n-bit input vector to a fixed threshold, while the other compares the Hamming weights of two independent vectors (of equal or different lengths). Such comparators find applications in median=rank rank filters, vector quantisers, and digital neural networks. Introduction: Given a binary vector a ¼ a1a2    an, its Hamming weight HA is defined as the number of ‘1’s’ in a. The circuits described below can compare HA to either a fixed threshold t, or to the Hamming weight HB of another vector, b ¼ b1b2    bm. Such comparators find applications in the fields of neural networks [1] and median=rank filters [2–4], among others. To perform the fixed-threshold computation described above, n!=t!(n  t)! comparisons are required. In terms of hardware, it means that n!=t!(n–t)! branches, of t transistors each (except for minor simplifications), would be needed to perform the computation in a truly parallel form, as shown in Fig. 1 (for n ¼ 6 and t ¼ 3, where a pseudo-CMOS gate was employed). In Fig. 1, X ¼ ‘1’ if HA  3, and X ¼ ‘0’ otherwise. Though in this example (n ¼ 6, t ¼ 3) only 20 branches are required, parallel implementations for more usual vector sizes are forbiddingly large (and slow, eventually); for instance, for n ¼ 16 and t ¼ 4 a total of 1820 branches would be needed. a1 a2 a3 a4 a5 a6 X Fig. 2 Fixed-threshold Hamming comparator (for n ¼ 6, t ¼ 3) Inset: A node X ¼ ‘1’ if HA  t Fig. 1 Parallel fixed-threshold Hamming comparator (for n ¼ 6, t ¼ 3) Linear complexity fixed-threshold comparator: A ripple-type implementation is proposed in Fig. 2. The number of rows is equal to t (or n–t, whichever is smaller), thus of the same order as in Fig. 1. However, the number of columns is now just n (linear). As shown in the inset of Fig. 2, each node of the matrix consists of just two switches, one vertical and one horizontal, which are implemented by means of trivial NOR plus NOT gates. The principle of operation is straightforward. The left end of each row in Fig. 2 is connected to VDD, so all rows are initially high. Let us then consider the input vector, from left to right (i.e. from a1 to a6). If a ‘1’ is found in it (starting from the left), it will cause the first row to change its logic level from ‘1’ to ‘0’ from that ‘1’s’ position all the way up to the gate of the output transistor. The next ‘1’ (if it exists) will cause the second row to change from ‘1’ to ‘0’ from that bit’s position up to the output transistor. Finally, a third ‘1’ would cause the third row to change from ‘1’ to ‘0’ from its position up. Since there are only three rows in this example (t ¼ 3), whenever three or more ‘1’s’ are present in the input vector they will cause the right end of all rows to be low, hence deactivating all nMOS transistors of the output gate, resulting in X ¼ ‘1’ at the output (again, a pseudo-CMOS gate was employed at the output to illustrate the operation of the comparator). Notice that Fig. 2 could be simplified. The OR gate at the output is indeed unnecessary, because all we need to do is monitor row 3. Additionally, the gates in the lower left corner (below the diagonal) can be suppressed. However, the structure, as shown, allows the operation with 2 vectors (described next). Linear complexity two-vector comparator: We now make use of the principle presented in Fig. 2 to introduce a two-vector Hamming comparator. The architecture is shown in Fig. 3, for n ¼ m ¼ 5, being the nodes of the matrix equal to that shown in the inset of Fig. 2. Therefore, the resulting circuit is very compact, simpler than any Fig. 3 Two-vector Hamming comparator (for n ¼ m ¼ 5) X ¼ ‘1’ if HA  HB Fig. 4 Spice simulations (circuit of Fig. 2, n ¼ 8, t ¼ 3, AMI 0.8 m CMOS process) The operation is as follows. Each ‘1’ present in vector b acts in the same way as VDD acts on the left end of each row in the fixed-threshold circuit of Fig. 2, i.e. HB establishes the value of t. Therefore, X ¼ ‘1’ if HA  HB, and X ¼ ‘0’ otherwise. Results: Spice results from a fixed-threshold circuit (Fig. 2) for n ¼ 8 and t ¼ 3 are shown in Fig. 4. AMI 0.8 m CMOS parameters were employed. The sizes of the transistors were 3=2 (in units of lambda) for all nMOS transistors, and 6=2 for all pMOS (true CMOS gates were employed in the horizontal and vertical switches), except for the ELECTRONICS LETTERS 27th November 2003 Vol. 39 No. 24 pull-up transistor at the output, the size of which was 3=6. Two intermediate bits (inputs 4 and 5) received a fixed ‘1’, while a pulse was applied to either input 1 (leftmost) or input 8 (rightmost), with the purpose of observing, besides the overall operation of the circuit, its propagation delay in the worst case (16 ns) and best case (7 ns), respectively (1.3 ns=stage). # IEE 2003 Electronics Letters Online No: 20031054 DOI: 10.1049/el:20031054 4 September 2003 References 1 2 3 4 ALEKSANDER, I., and MORTON, H.: ‘An introduction to neural computing’ (Chapman & Hall, London, 1995) KAR, B.K., and PRADHAN, D.K.: ‘A new algorithm for order statistic and sorting’, IEEE Trans. Signal Process., 1993, 41, (8), pp. 2688–2694 KING, D.B.S., SIMPSON, R.J., MOORE, C., and MACDIARMID, I.P.: ‘Digital ntupple Hamming comparator for weightless systems’, Electron. Lett., 1998, 34, (22), pp. 2103–2104 KING, D.B.S., SIMPSON, R.J., MOORE, C., and MACDIARMID, I.P.: ‘Hamming value comparator hierarchies’, Electron. Lett., 1999, 35, (11), pp. 910–911 V.A. Pedroni (Department of Electronics Engineering, Federal Center of Technological Education of Parana (CEFET-PR), Av. Sete de Setembro, 3165, CEP 80230-901 Curitiba, PR, Brazil ) E-mail: [email protected] ELECTRONICS LETTERS 27th November 2003 Vol. 39 No. 24

References (4)

  1. ALEKSANDER, I., and MORTON, H.: 'An introduction to neural computing' (Chapman & Hall, London, 1995)
  2. KAR, B.K., and PRADHAN, D.K.: 'A new algorithm for order statistic and sorting', IEEE Trans. Signal Process., 1993, 41, (8), pp. 2688-2694
  3. KING, D.B.S., SIMPSON, R.J., MOORE, C., and MACDIARMID, I.P.: 'Digital n- tupple Hamming comparator for weightless systems', Electron. Lett., 1998, 34, (22), pp. 2103-2104
  4. KING, D.B.S., SIMPSON, R.J., MOORE, C., and MACDIARMID, I.P.: 'Hamming value comparator hierarchies', Electron. Lett., 1999, 35, (11), pp. 910-911
About the author
Papers
65
Followers
59
View all papers from Volnei Pedroniarrow_forward