METHOD AND APPARATUS FOR SIGNAL SPECTRUM ANALYSIS BY HADAMARD TRANSFORM

• US 3,859,515 A
• Filed: 10/02/1973
• Issued: 01/07/1975
• Est. Priority Date: 08/21/1972
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Arthur J. Radcliffe Jr
• Inventors: Radcliffe, Arthur J. Jr.
• Primary Examiner(s): Gruber, Felix D.
• Assistant Examiner(s): Malzahn, David H.
• Application Number:
  US05/402,723
• Time in Patent Office: 462 Days
• Field of Search: 235/164,156 340/146.3A,146.3R,146.3Q,146.3SY,149R 324/77R
• US Class Current: 708/410
• CPC Class Codes: G06F 17/145 Square transforms, e.g. Hadamard, Walsh, Haar, Hough, Slant transforms
• CPC Class Codes: G06V 10/431 Frequency domain transformation; Autocorrelation
• CPC Class Codes: G06V 40/382 Preprocessing; Feature extraction

Abstract

A method and apparatus for transforming the analog waveform of a signal into its Hadamard characterization by performing a matrix multiplication using the Hadamard matrix and for analyzing the resulting Hadamard characterization of the signal for identification purposes. A parallel adder system employing recirculating shift registers utilizes the unique properties of the Hadamard matrix so as to reduce the matrix multiplication required in the transformation to a minimal number of simple addition and subtraction operations.

Claims

1. Apparatus for providing a Hadamard characterization of an analog signal comprising:

means for providing a digital representation of an analog signal;

means for sequentially generating the elements of the Hadamard matrix;

storage means; and

adder means coupled to said means for providing a digital representation, to said Hadamard matrix generator and to said storage means, said adder means responsive to the value supplied by said Hadamard matrix generator for adding the digital representation of said analog signal to the value stored in said storage means when said Hadamard matrix element is positive and for subtracting the digital representation from the value stored in said storage means when said Hadamard matrix element is negative.

2. The apparatus of claim 1 wherein said adder means includes a parallel adder having a first set of inputs for receiving, in parallel, said digital representation, a second set of inputs for receiving, in parallel, the value stored in said storage means, and a third input for receiving elements of the Hadamard matrix.

3. The apparatus of claim 2 wherein said means for generating the values of the Hadamard matrix includes a memory means for storing the values of the Hadamard matrix and for recalling the stored values in a predetermined sequence.

4. The apparatus of claim 2 wherein said means for providing a digital representation of the analog signal includes analog-to-digital conversion means for sampling the original analog signal and means for storing a binary number representing the sampled value.

5. The apparatus of claim 4 wherein said means for storing a binary number includes a binary counter means having parallel output means coupling each of the bit positions of said binary counter means to said first set of inputs of said parallel adder means.

6. The apparatus of claim 2 wherein said adder means further includes output means for receiving the result of the addition or subtraction and for storing said result back into said storage means.

7. The apparatus of claim 6 wherein said storage means includes a plurality of parallel shift registers, there being an individual shift register for each bit position required in the Hadamard characterization of the analog signal and wherein each register includes a number of bit positions equal to the number of rows or columns in the Hadamard matrix being utilized.

8. The apparatus of claim 7 wherein said storage means includes a one bit buffer means having a bit position coupled to a corresponding one of said parallel shift registers and an output from each of the positions of said one bit buffer means coupled to a corresponding one of said second set of input means.

9. The apparatus of claim 8 wherein said storage means further includes means for coupling the outputs of said plurality of parallel shift registers to a corresponding bit position in said one bit buffer and means for coupling the output of a corresponding bit position in said one bit buffer to a corresponding bit position in the parallel adder means;

and wherein the output means of said adder means includes means for coupling the output of the parallel adder back to corresponding inputs of said plurality of parallel shift registers to form a recirculating configuration.

10. Apparatus for verifying the authenticity of a handwritten signature by comparing an electrical characterization of the handwritten signature to be tested with a pre-recorded value or known specimen, said apparatus comprising:

means for converting the pressure variations involved in generating a handwritten signature into an electrical analog signal;

means for generating a digital representation of the analog signal;

means for performing a Hadamard transform on the digital representation of the electrical analog signal; and

means for comparing the Hadamard characterization of the signature produced as the result of performing the Hadamard transform on the digital representation of the electrical analog signal with said pre-recorded value.

11. The apparatus of claim 10 wherein said comparison means includes a means for indicating whether or not the authenticity of the handwritten test signature is verified;

and wherein said means for converting pressure variations includes pressure-responsive transducer means.

12. The apparatus of claim 10 wherein said means for performing a Hadamard transform includes:

means for generating a binary number representing a sampled value in the analog waveform;

means for generating Hadamard matrix signals;

recirculating shift register means for storing partial sums; and

adder means responsive to said Hadamard matrix signals for adding said generated binary number to and subtracting said binary number from a preselected one of the partial sums stored in said recirculating shift register means.

13. In a signature verification system wherein an individual'"'"''"'"'s handwritten signature which is to be tested is converted into a test vector which is to be compared to a stored vector representing a particular individual'"'"''"'"'s known signature, the improvement comprising:

means for performing a Hadamard transform on said test vector to produce a set of values comprising a transformed test vector; and

means for comparing said transformed test vector with said stored vector to determine the authenticity of the tested handwritten signature.

14. An apparatus for multiplying a one dimensional matrix having n elements by an n X n Hadamard matrix comprising:

means for generating the elements of the Hadamard matrix in a predetermined sequence;

means for initially selecting the first element of the one dimensional matrix and for subsequently selecting the next successive element whenever n Hadamard matrix elements have been generated;

means for storing n partial sums and for addressing the next successive partial sum whenever another Hadamard element has been generated;

adder means coupled to said selecting, generating and storing means and responsive to the generation of a positive Hadamard element for adding the selected element of the one dimensional matrix to the currently addressed partial sum and responsive to the generation of the negative Hadamard matrix element for subtracting the selected element of the one dimensional matrix from the currently addressed partial sum.

15. The apparatus of claim 14 wherein said means for generating the elements of the Hadamard matrix includes means for assuring that the elements are generated in a sequential order beginning with the first row of the first column of the Hadamard matrix and proceeding down the elements of each of the columns until the nth value of a column has been reached and then proceeding to the first row of the next successive column and down the column until the nth element of the nth column has been generated.

16. The apparatus of claim 14 wherein said means for selecting elements of the one dimensional matrix includes binary counter means for storing the binary representation of a number and means for outputting the binary number in a bit parallel manner.

17. The apparatus of claim 16 wherein said adder means includes a parallel adder having a first set of inputs for receiving in a bit parallel manner the binary number stored in said selecting means, a second set of inputs for receiving in a bit parallel manner the values currently stored in a selected one of said n partial sums, and a third input means for sequentially receiving the generated elements of the Hadamard matrix.

18. The apparatus of claim 17 wherein said adder means further includes output means for receiving the value resulting when said selected element is added to or subtracted from the value stored in a partial sum and for transferring this resulting value back to said means for storing partial sums in a recirculating fashion.

19. The apparatus of claim 18 wherein said means for storing and addressing partial sums includes a set of parallel shift registers, the output of each being coupled to the second set of inputs of the parallel adder and the output means of the parallel adder being coupled back to the inputs of the set of parallel shift registers, each one of said set of parallel shift registers having n bit positions such that each one of the bit positions of a particular parallel shift register stores one bit of the partial sum.

20. A method of signature identification employing a pre-recorded coded representation of a reference signature, said method comprising the steps of:

converting pressure variations inherent in the actual writing of a handwritten signature to be tested into an electrical analog signal;

sampling the electrical analog signal to produce a digital representation thereof;

generating, in a predetermined column-by-column sequence, the elements of the Hadamard matrix;

storing, in a predetermined sequence, the elements of a set of values representing said digital representation such that a new element of said set of values will be stored before the first element of a new column of the Hadamard matrix is generated;

forming partial sums by adding said stored element of said set of values representing said digital representation to a partial sum for every occurrence of a positive Hadamard element, and for subtracting said stored element of said set of values representing said digital representation from said partial sum for the occurrence of every negative Hadamard element until all of the elements of the Hadamard matrix have been generated; and

comparing the Hadamard transformed set of values representing the handwritten signature to be tested which is represented by the final partial sums with the pre-recorded coded representation of the reference signature for identification purposes.

21. In a system for verifying the authenticity of a handwritten signature to be tested, said system including means for providing a pre-recorded set of values representing a particular known handwritten signature and pressure transducer means for converting the pressure variations inherent in writing a handwritten signature to be tested into an electrical analog waveform, a method of signature verification comprising the steps of:

sampling the electrical analog waveform for producing a set of digital values;

performing a Hadamard transformation on the set of digital values; and

comparing the set of transformed values with said pre-recorded set of values for identification purposes.

22. A method of multiplying a one dimensional matrix having n elements (V1, V2, . . . Vn) by an n X n Hadamard matrix comprising the steps of:

storing the first element of said one dimensional matrix;

sequentially generating the individual elements of the first column of said n X n Hadamard matrix;

adding the value of said stored first element of said one dimensional matrix to one of a set of n subtotals for each positive element in the column of the Hadamard matrix being generated and subtracting the value of said stored first element from one of said set of n subtotals for each negative element in the column of the Hadamard matrix being generated, the particular one of said set of n subtotals corresponding to the numbered position of the element in the column of the Hadamard matrix currently being generated;

removing said stored element and storing the next successive element when the nth element of the seLected column of the Hadamard matrix has been generated;

sequentially generating the individual elements of the next successive column of the Hadamard matrix;

adding the value of said stored element to one of a set of n subtotals for each positive element in the column of the Hadamard matrix being generated and subtracting the value of said stored element from one of a set of n subtotals for each negative element in the selected column of the Hadamard matrix being generated; and

repeating said steps of storing an element, sequentially generating the individual elements of the next successive column of the Hadamard matrix and adding and subtracting in accordance with the sign of the Hadamard elements until the nth element of the one dimensional matrix has been stored and the nth element of the nth column of Hadamard matrix has been processed, at which time the set of n subtotals will contain the results of the Hadamard multiplication.