Charge domain block matching processor

• US 5,030,953 A
• Filed: 07/11/1990
• Issued: 07/09/1991
• Est. Priority Date: 07/11/1990
• Status: Expired due to Term

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Chiang, Alice M.
• Primary Examiner(s): Pellinen, A. D.
• Assistant Examiner(s): WILLIAMS, HOWARD L
• Application Number:
  US07/551,947
• Time in Patent Office: 363 Days
• Field of Search: 365/194, 365/183, 365/49, 341/172, 341/150, 358/11, 358/12, 358/105, 358/140, 358/141, 364/602, 364/604, 364/606, 364/862
• US Class Current: 341/172
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation

Abstract

A full search block matching algorithm includes a charge-domain serial tapped delay line as an input buffer, and an array of charge domain signal processors. The delay line shifts and holds analog sampled data which are in the form of charge packets. At each stage of delay, the signals are nondestructively sensed and coupled to a corresponding signal processor, and the sampled data are transferred and subsequently processed in parallel. The processed data from all the processors can be read out either in a parallel or serial format through a parallel-in-serial-out output buffer. In this structure, only the serial input buffer has to be clocked at the system throughout rate; the internal clock rate of each processor is reduced by the number of parallel processors. Within each processor, all of the computation functions are performed in the charge domain, and local charge domain memories are included for storing the processed signal.

Claims

1. A full search block matching processor for determining the best matching m×

n element subarray of an M×

N element array with an m×

n element template, where m≦

M and n≦

N, comprising;

A. a charge domain tapped delay line including;

i. at least (m×

n)+(m-l)×

(N-n) stages and having a serial input channel and m groups of n parallel output channels, each of said n output channels in each group being coupled to an associated one of n successive stages in a corresponding group of stages in said delay line, wherein each of said groups of n successive stages in said delay line are separated by N-n successive stages in said delay line,

ii. means for establishing a succession of at least m×

n charge packets in said delay line in response to a succession of applied input signals, each of said packets having a magnitude corresponding to an associated one of a corresponding succession of elements of said array,

iii. means for shifting said charge packets from stage-to-stage along said delay line at an input rate, and

iv. N floating gate sensing electrodes, each of said electrodes overlying one of said stages and being adapted to provide a potential thereon representative of the magnitude of a charge packet currently within its underlying stage, said potential being a search signal associated with said electrode,

B. a template network including;

i. a charge storage region and an associated means for establishing a succession of m×

n charge packets in said storage region at said input rate, each of said packets having a magnitude corresponding to an associated element in said template,

ii. a floating gate sensing electrode overlying said storage region and being adapted to provide a potential thereon representative of the magnitude of a charge packet currently underlying said electrode, said potential being a template signal,

C. m groups of n charge domain absolute magnitude difference (AMD) networks, each of said AMD networks;

i. having a template input port, a search input port, and a charge domain output port, wherein each of the n AMD networks of each of said groups has its search input port coupled to an associated sensing electrode of an associated group of said output channels of said delay line, and has its template input port coupled to said sensing electrode of said template network,

ii. each of said AMD networks includes means for providing at its output port a succession of charge packets at said input rate, each of said charge packets being representative of the absolute magnitude of the difference between the current one of said search signals at its search input port and the current one of said template signals at said template input port,

D. m groups of n charge domain summing networks, each of said summing networks;

i. being associated with an AMD network in an associated one of said m groups of AMD networks, and

ii. including means for providing at an output thereof a succession of output charge packets at a summing rate equal to 1/(m×

n) times said input rate, each of said output charge packets having a magnitude representative of the sum of the magnitude of m×

n successive charge packets provided at said output port of said associated AMD network,

E. m charge domain row accumulator networks, each row accumulator network;

i. being associated with one of said m groups of n AMD networks, and

ii. including means for substantially simultaneously receiving said output charge packets of its associated n summing networks at distinct locations in said row accumulator network, and

iii. means for transferring said received charge packets to establish a succession of said output charge packets at an output port thereof at an accumulator rate equal to l/m times said input rate,

F. m charge domain row minimum difference (MD) networks, each row MD network;

i. being associated with one of said m row accumulator networks, and

ii. including means for storing a charge packet therein, and

iii. including means for receiving said succession of said output charge packets one at a time at said accumulator rate, and means operative at the receipt of each of said charge packets for retaining and storing only the smaller magnitude one of said just received charge packet and a previously stored charge packet,

G. a charge domain column accumulator network, said column accumulator network;

i. being associated with said m row MD networks, and

ii. including means for substantially simultaneously receiving said stored charge packets of said m row MD networks at distinct locations in said column accumulator network, and

iii. means for transferring said received charge packets to establish a succession of output charge packets at an output port thereof at a rate equal to said accumulator rate, and

H. a charge domain column minimum difference (MD) network, said column MD network;

i. being associated with one of said column accumulator networks, and

ii. including means for storing a charge packet therein, and

iii. including means for receiving said succession of said output charge packets one at a time at said accumulator rate, and means operative at the receipt of each of said charge packets for retaining and storing only the smaller magnitude one of said just received charge packet and the next previously stored charge packet,

whereby the magnitude of said charge packet stored at said column MD network is representative of said best matching m×

n subarray of said elements that have been represented by charge packets in said delay line.

2. A processor according to claim 1 further comprising:

identifying means for identifying which m×

n charge packet of said charge packets established in said delay line generates said stored charge packet in said column MD network.

3. A processor according to claim 2 wherein said identifying means includes:

means for identifying the AMD network which provides the minimum magnitude charge packet of said charge packets provided by its associated n row MD networks for each set of m×

n input clock rate pulses, and

means for identifying the row MD network which provides the minimum magnitude charge packet of said charge packets provided by said m row MD networks.

4. A processor according to claim 1 wherein N=31, M=31, m=16 and n=16.

5. A full search block matching processor for determining the best matching m×

n element subarray of an M×

N element array with an m×

n element template, where m≦

M and n≦

N, comprising;

A. a charge domain tapped delay line including;

i. at least (m×

n)+(m-l)×

(N-n) stages and having a serial input channel and m groups of n parallel output channels, each of said n output channels in each group being coupled to an associated one of n successive stages in a corresponding group of stages in said delay line, wherein each of said groups of n successive stages in said delay line are separated by N-n successive stages in said delay line,

ii. means for establishing a succession of at least m×

n charge packets in said delay line in response to a succession of applied input signals, each of said packets having a magnitude corresponding to an associated one of a corresponding succession of elements of said array,

iii. means for shifting said charge packets from stage-to-stage along said delay line at an input rate, and

iv. N floating gate sensing electrodes, each of said electrodes overlying one of said stages and being adapted to provide a potential thereon representative of the magnitude of a charge packet currently within its underlying stage, said potential being a search signal associated with said electrode,

B. a template network including;

i. a charge storage region and an associated means for establishing a succession of m×

n charge packets in said storage region at said input rate, each of said packets having a magnitude corresponding to an associated element in said template,

ii. floating gate sensing electrode overlying said storage region and being adapted to provide a potential thereon representative of the magnitude of a charge packet currently underlying said electrode, said potential being a template signal,

C. m groups of n charge domain absolute magnitude difference (AMD) networks, each of said AMD networks;

i. having a template input port, a search input port, and a charge domain output port, wherein each of the n AMD networks of each of said groups has its search input port coupled to an associated sensing electrode of an associated group of said output channels of said delay line, and has its template input port coupled to said sensing electrode of said template network,

ii. each of said AMD networks includes means for providing at its output port a succession of charge packets at said input rate, each of said charge packets being representative of the absolute magnitude of the difference between the current one of said search signals at its search input port and the current one of said template signals at said template input port,

D. m groups of n charge domain summing networks, each of said summing networks;

i. being associated with an AMD network in an associated one of said m groups of AMD networks, and

ii. including means for providing at an output thereof a succession of output charge packets at a summing rate equal to 1/(m×

n) times said input rate, each of said output charge packets having a magnitude representative of the sum of the magnitude of m×

n successive charge packets provided at said output port of said associated AMD network,

E. m charge domain row accumulator networks, each row accumulator network;

i. being associated with one of said m groups of n AMD networks, and

ii. including means for substantially simultaneously receiving said output charge packets of its associated n summing networks at distinct locations in said row accumulator network, and

iii. transferring said received charge packets to establish a succession of said output charge packets at an output port thereof at an accumulator rate equal to 1/m times said input rate,

F. a charge domain column accumulator network, said column accumulator network;

i. being associated with said m row accumulator networks, and

ii. including means for substantially simultaneously receiving said succession of output charge packets of said m row accumulator networks at distinct locations in said column accumulator network, and

iii. means for transferring said received charge packets to establish a succession of output charge packets at an output port thereof at a rate equal to said input rate, and

G. a charge domain column minimum difference (MD) network, said column MD network;

i. being associated with said column accumulator network, and

ii. including means for storing a charge packet therein, and

iii. including means for receiving said succession of said output charge packets one at a time at said input rate, and means operative at the receipt of each of said charge packets for retaining and storing only the smaller magnitude one of said just received charge packet and the next previously stored charge packet,

whereby the magnitude of said charge packet stored at said column MD network is representative of said best matching m×

n subarray of said elements that have been represented by charge packets in said delay line.

6. A processor according to claim 5 further comprising:

identifying means for identifying which m×

n charge packet of said charge packets established in said delay line generates said stored charge packet in said column MD network.

7. A processor according to claim 6 wherein said identifying means includes:

means for identifying the AMD network which provides the minimum magnitude charge packet of said charge packets provided by its associated n row MD networks for each set of m×

n input clock rate pulses, and means for identifying the row MD network which provides the minimum magnitude charge packet of said charge packets provided by said m row MD networks.

8. A processor according to claim 5 wherein N=31, M=31, m=16 and n=16.