Serial correlator architecture

An apparatus for correlating multibit first and second words includes a multiplexer for selecting one bit at a time of the second word, and applying the bit to a multiplier which receives the first word, for generating a product by inverting or noninverting the first word. The product is applied to an adder and is added to a delayed parallel signal to produce a sum signal. The sum signal is delayed in an amount related to the number of bits in the first word to produce the delayed parallel signal. A plurality of such apparatuses are cascaded, with the bits of the second word applied in subsets to the apparatuses, and the partial correlations applied as input words to the next apparatus in the cascade.

FIELD OF THE INVENTION

A correlator architecture performs correlation between digital signals using a particular architecture including multiplexers and multipliers.

BACKGROUND OF THE INVENTION

Correlation is widely used in signal processing, to help to identify the presence of particular signal sequences. One form of correlation is described in the context of a radar system in U.S. Pat. No. 5,376,939, issued Dec. 27, 1994 in the name of Urkowitz.

Correlation processing is described generally by the equation
Rxy=∫X(n)Y(n−k)dn(1)
and discrete correlation can be represented by

Structure10ofFIG. 1aillustrates a portion of a prior-art correlator structure which is well adapted to being fabricated on or in an Application-Specific Integrated Circuit (ASIC). ASICs are advantageous in that the desired structure can be selected and optimized in a relatively small integrated circuit. However, ASICs have long design and fabrication cycles, and can be expensive, especially if the number of units to be fabricated is small.

Structure10ofFIG. 1aillustrates a portion of a correlator structure which is well adapted for fabrication on an ASIC. InFIG. 1a, a source1of first signal produces parallel signal, designated Y, and applies it by way of a path1pto an input port10i1of a correlator illustrated as a block10. A source2of second signal produces parallel signal on a path2pfor application to a second input port10i2of correlator block10. Correlator10correlates the first signals Y with the second signals X and produces at its output port10oa signal Rxy representing the correlation.

FIG. 1billustrates details of one possible prior art embodiment of correlator10ofFIG. 1a. InFIG. 1b, correlator10includes a clocked multibit register (R) which, at each cycle of a clock signal, gates or couples the bits of a first Y word onto a multibit bus14. Correlator10also includes a set of multipliers (X)160,161,162, . . . ,16N−1of a set16of multipliers. Each multiplier of set16includes two input ports, one of which is a multibit input port, and one of which is a single-bit input port. More particularly, multiplier160includes a multibit input port16i10, multiplier161includes a multibit input port16i11, multiplier162includes a multibit input port16i12, . . . , and multiplier16N−1includes a multibit input port16i1N−1. The single-bit input ports of multipliers160,161,162, . . . ,16N−1are designated16i20,16i21,16i22, . . . ,16i2N−1, respectively. All the bits of the Y word coupled onto bus14from register12are applied to the multibit first input ports of all the multipliers. That is, when a particular Y word appears on bus14, all the bits of that Y word are applied to each of multibit input ports16i10,16i11,16i12, . . . , and16i1N−1. For each Y word coupled to the multibit input ports of set16of multipliers ofFIG. 1b, the bits of a word are individually applied to the single-bit input ports16i20,16i21,16i22, . . . ,16i2N−1of multiplier set16. The single-bit inputs can be viewed as being “control” bits which determine the state of the multiplier. In short, each multiplier160,161,162, . . . ,16N−1of set16multiplies the Y word applied to its multibit input port by either +1 or −1, depending upon the state of the “control” X bit applied to its single-bit input port. Thus, if the single X bit applied to input port16i20of multiplier160is a logic high (+1), the multibit Y word applied to its multibit input port16i10is translated without change by way of a multibit path180to an input port20i10of an adder200, where it is added to any multibit word applied by way of a path220to an input port20i20. As illustrated, the value of the word applied by way of a path220to input port20i20of adder200is zero. In a similar manner, the multibit Y word appearing on bus14is coupled simultaneously to first input ports16i11,16i12, . . . , and16i1N−1of the remaining multipliers161,162, . . . ,16N−1of set16, and each multiplier of set16multiplies the Y word by either +1 or −1 depending upon the state of the single bit of X input signal applied to the corresponding second input ports16i20,16i21,16i22, . . . ,16i2N−1, and the resulting inverted or noninverted versions of the multibit Y signal or word are coupled to adders200,201,202, . . . ,20N−1of a set20of adders. Thus, the multiplied (that is, inverted or noninverted) multibit Y word from multiplier160is applied over path180to input port20i10of adder200, the multiplied multibit Y word from multiplier161is applied over path181to input port20i11of adder201, the multiplied multibit Y word from multiplier162is applied over path182to input port20i12of adder202, . . . , and the multiplied multibit Y word from multiplier16N−1is applied over path18N−1to input port20i1N−1of adder20N−1. Each adder200,201,202, . . . ,20N−1of set20of adders sums the multiplied multibit Y word (the addend) received from its associated multiplier160,161,162, . . . ,16N−1of set16of multipliers with or to the multibit number (the augend) applied to its second input port. Thus, the addend applied to input port20i10of adder200is summed with the augend applied to input port20i20of adder200to produce a sum which is applied to a register (R)240of a set of registers24, the addend applied to input port20i11of adder201is summed with the augend applied to input port20i21of adder201to produce a sum which is applied to a register (R)241, the addend applied to input port20i12of adder202is summed with the augend applied to input port20i22of adder202to produce a sum which is applied to a register (R)242, . . . , and the addend applied to input port20i1N−1of adder20N−1is summed with the augend applied to input port20i2N−1of adder20N−1to produce a sum which is applied to a register (R)24N−1. Each register240,241,242, . . . ,24N−1of set24of registers delays the coupling of the sum from the previous adder by one clock cycle. The correlation output appears at the output port100of register24N−1.

In operation of the arrangement10ofFIG. 1b, a new Y digital word is applied from register12to bus14at each clock cycle. At each clock cycle, the bits of a new X digital word are applied to the various bit input ports of multibit port or path2p, and a multiplication occurs in the multipliers of set16. The product is applied to the adders of set20and is added during the same clock cycle. This produces a sum at the output of each adder or summer of set20of adders. At the next clock cycle, the registers of set20each transfer the sum from its associated lower-numbered summer to the augend input port of the next higher-numbered adder. All registers are clocked at the same time. Parallel data Y changes on a clock-to-clock basis, but the X value does not change unless or until a different correlation is to be processed. All multiplications and additions occur on a clock-to-clock basis, and the intermediate results are stored in registers on a clock-to-clock basis. Hence the resultant output Rxyoccurs on a clock-to-clock basis in a continuous stream until all Y values have been processed. On each clock cycle, the resultant output is the correlated output of Y to X, after the first initial N clocks. As an example if N is 8, it will take 8 clock cycles for valid correlated output to propagate to the resultant output. That is, correlated output appears at port10oonly after the first N clock cycles have passed.

In some computation-intensive applications, the words being processed may contain thousands of bits. Such large numbers of processing steps can be accommodated in a reasonable number of ASICs. However, in some contexts it may be desirable to use Field Programmable Gate Arrays (FPGAs) gate-programmable arrays instead of ASICs. Field Programmable Gate Arrays are advantageous in that they are commercially made in large numbers, and are both inexpensive and reliable. A disadvantage of Field Programmable Gate Arrays is that by nature each integrated circuit contains elements which are useful for the desired function, and also contains elements which may be less useful, or not at all useful. Consequently, more Field Programmable Gate Arrays FPGAs may be required, in order to perform correlations with words containing large numbers of bits, than is desirable for reasons of bulk and interconnection complexity.

Improved or alternative correlator arrangements are desired.

SUMMARY OF THE INVENTION

An apparatus for correlating multibit first and second signals includes a multiplexer including a multibit input port coupled to receive the second signal, and also including a single-bit output port, for selectively coupling to its output port one bit at a time of the multibit second signal. A multiplier includes an output port, a first multibit input port and second single-bit input port. The single-bit input port is coupled to the output port of the multiplexer. The multiplier is coupled for receiving the first digital signals in parallel form, for controllably coupling to its output port a multibit product signal in response to the one bit of a second signal applied to its second input port. The multiplier, in another embodiment, multiplies the words of the first signal by +1 if the one bit of the second digital signal applied to its second input port has a logical value of 1 and by −1 if the one bit of the second digital signal applied to its second input port has a logical value of 0. The multiplier, in one embodiment, multiplies the words of the first signal by −1 if the one bit of the second digital signal applied to its second input port has a logical value of 1 and by +1 if the one bit of the second digital signal applied to its second input port has a logical value of 0. The apparatus further includes summing means including an input port coupled to the output port of the multiplier, for summing the multibit product signals received from the multiplier with delayed parallel signals, to thereby produce summed parallel signals representing the correlated output. A delay means or arrangement is coupled to receive the summed parallel signals, for delaying the summed parallel signals for a number of clock cycles equal to the number of bits in the digital first signals, for thereby producing the delayed parallel signals.

In a particular embodiment of the arrangement, means are provided for coupling the words of the second signal to the first input port of the multiplier. The means may comprise a register clocked rate Clk/N lower than that of the multiplexer.

A particular embodiment of the arrangement further comprises a register having an input port coupled to receive the summed parallel signals representing the correlated output.

In another embodiment, the means for coupling the words of the first signal to the first input port of the multiplier comprises a first register clocked at a rate lower than that of the first multiplexer. This embodiment further comprises a clocked second register having an input port coupled to receive the summed parallel signals representing the correlated output, with the second register being clocked at the same rate as the first register. Initialization or cascading of the correlation apparatus may be provided by an embodiment which further comprises second multiplexing means coupled to the summing means, for applying an initialization value to the summing means.

A method for correlating first and second multibit signals includes the step of applying the first signals to a first input port of a multiplier, where the multiplier includes a single-bit second input port and an output port for a period of at least N clock cycles. The bits of the multibit second signal are gated to the single-bit second input port of the multiplier, for sequentially multiplying the first input signal by the individual bits of the second input signal, for thereby producing multiplied multibit signals. The multiplied multibit signals are applied to a first input port of an adder, which adder includes a second input port for receiving delayed signals, and also includes an output port at which added signals are generated. The added signals are delayed by a number of clock cycles at least equal to the number of bits in the first multibit signal, to thereby produce delayed signals. The delayed signals are applied to the second input port of the adder, whereby the added signals include the result of the correlation. The results of the correlation are extracted from the added signals.

An apparatus according to an aspect of the invention is for correlating M-bit first and second signals. The apparatus comprises a plurality of N-bit correlators, where N is less than M. Each of the N-bit correlators of the plurality comprises(a) an N-bit multiplexer including an N-bit input port coupled to receive a subset of bits of the M-bit second signal, and also including a single-bit output port, for selectively coupling to its output port one bit at a time of the subset of bits;(b) a multiplier including an output port, a first multibit input port and second single-bit input port, the single-bit input port of the multiplier being coupled to the output port of the multiplexer for receiving the one bit at a time, the multiplier being coupled for receiving the first signals in parallel form at its first input port, for controllably coupling to its output port a multibit product signal in response to that one bit of the second signal applied to its second input port, and for one of (a) multiplying the words of the first signal by +1 if the one bit of the second digital signal applied to its second input port has a logical value of 1 and by −1 if the one bit of the second digital signal applied to its second input port has a logical value of 0, and (b) multiplying the words of the first signal by −1 if the one bit of the second digital signal applied to its second input port has a logical value of 1 and by +1 if the one bit of the second digital signal applied to its second input port has a logical value of 0;(c) summing means including an input port coupled to the output port of the multiplier, for summing the multiplied parallel signals received from the multiplier with delayed parallel signals, to thereby produce summed parallel signals representing the correlated output; and(d) delay means coupled to receive the summed parallel signals, for delaying the summed parallel signals for a number of clock cycles at least equal to the number of bits in the digital first signals, for thereby producing the delayed parallel signals.
The apparatus according to this aspect of the invention includes means for selectively applying the summed parallel signals representing the correlated output from one of the N-bit correlators to the next one of the N-bit correlators in the cascade.

A method according to another aspect of the invention is for correlating first and second multibit signals. The method comprises the step of applying the multibit first signals to a first input port of a multiplier which includes a single-bit second input port and an output port. The method further includes the step of, while the multibit first signals are applied to the first input port of the multiplier, sequentially gating the bits of the multibit second signal to the single-bit second input port of the multiplier, for sequentially multiplying the first input signal by the individual bits of the second input signal for thereby producing multiplied multibit signals. The multiplied multibit signals are applied to a first input port of an adder, which adder includes a second input port for receiving delayed signals, and an output port at which added signals are generated representing the sum of the multiplied multibit signals with the delayed signals. The added signals are delayed by a number of clock cycles at least equal to the number of bits in the first multibit signal, to thereby produce the delayed signals. The delayed signals are applied to the second input port of the adder, whereby the added signals include the result of the correlation. A particular mode of this method comprises the step of extracting the result of the correlation from the added signals.

DESCRIPTION OF THE INVENTION

FIG. 2shows an N-bit correlator which can be cascaded with M−1 other similar correlators to constitute a correlator capable of handling MN-bit signals.

The arrangement ofFIG. 2accepts the multibit Y words from a path1pat a register (R)212which is clocked or gated by a clock signal CLK/N, which occurs once every N CLK cycles, as illustrated inFIGS. 3aand3b. At each gating cycle, the multibit Y word is gated onto a multibit bus214and applied to a multiplier216. Multiplier216is similar to a multiplier of set16ofFIG. 1b, in that it includes a multibit input port216i1and a single-bit input port216i2, and it either inverts or noninverts (passes unchanged) the multibit Y signal applied to the multibit input port216i1depending upon the state of the single-bit signal applied to its single-bit input port216i2. The multiplied multibit signal produced by multiplier216ofFIG. 2is applied over a multibit path218to a first or addend input port220i1of an adder or summer designated220. Adder220adds the addend applied to its first input port220i1to the augend applied by way of a multibit path222to its second input port220i2, and produces a summed signal at its output port220o. The summed signal produced by adder220includes the correlation signal, which is applied to a clocked output register (R)240, which clocks the correlation signal RXYfrom an output port210oto a user apparatus (not illustrated) by way of a path250.

The summed signal produced by adder220ofFIG. 2is also applied to a delay circuit designated generally as224, which includes a plurality of N clocked registers2240,2241, . . . ,224N−1. The delay circuit224delays the summed signal produced by adder220by N clock cycles, and applies the summed signal multibit bus222by way of a multibit multiplexer232. Multiplexer232is used for two different purposes. The first purpose is to initialize one section (the illustrated section) of the correlator210by applying a zero to bus222at the beginning of each correlation. The second purpose is to initialize the illustrated section of the correlator when it is used in a cascade with other such sections for handling multibit words having numbers of bits greater than N.

Correlator210ofFIG. 2also includes a further multiplexer designated230. Multiplexer230is clocked at the CLK rate, for applying one bit at a time of the multibit X signal to second input port216i2of multiplier216. Thus, multiplier216sequentially multiplies the same N-bit Y word by each bit of the X word, to produce a product for application to adder220. After the first N CLK cycles of operation, the delayed sum signal applied by way of bus222to second input port220i2of adder220in general has a nonzero value.

The step-by-step operation can be understood by reference toFIG. 2in conjunction with the CLK and CLK/N clock signals ofFIGS. 3aand3b, respectively.FIG. 3aillustrates the system clock CLK, andFIG. 3billustrates the reduced-rate clock CLK/N. The CLK pulses are numbered in two different ways, (a) by absolute number of cycles starting from zero value (that is, starting at 0 and proceeding monotonically to some number MN, where M is large), and (b) modulus N (that is, a repeating cycle of 0, 1, 2, 3, . . . N−1, N). Initially (that is, at CLK=0) all registers are cleared in the arrangement210ofFIG. 2. During Clock Cycle1ofFIGS. 3aand3b(corresponding to the 0thoccurrence of CLK ofFIG. 3aand the 0thoccurrence of CLK/N ofFIG. 3b), the value at the output port220oof adder220is stored in register240. Also during the 0thCLK/N clock cycle, a new multibit value of Y is stored in register212and becomes available on bus214, multiplexer230is set to output the single bit X(0), and multiplexer232is set to output a value of 0 from path221. Multiplier216multiplies the multibit word Y(0) with (by) bit X(0), which is the first bit of the X word. The inverted or noninverted product produced by multiplier216is applied to adder220, which adds zero from bus222with the product produced by multiplier216at port216o.

During the next CLK cycle, (the second occurrence of CLK ofFIG. 3aor CLK cycle1), the output from port220oof adder220is stored in shift register2240, and the contents of the registers of delay224shift toward the output of the delay (toward the left inFIG. 2). Also, multiplexer232is set to output the signal on path223, and multiplexer230is set to output X(1), the second bit of the X word. Multiplier216multiplies multibit word Y(0) with bit X(1) to produce the inverted or noninverted product at port216o. Adder220adds together the output of multiplexer232with product at the output port216oof multiplier216.

During the third clock cycle ofFIG. 3a, corresponding to CLK pulse2, the output from port220oof adder220is transferred into shift register2240, and the words stored in the other registers of delay224shift one register to the left. Multiplexer230is set to output bit X(2), which is the third bit of the X word. Multiplexer232is set to couple the output of register224n−1onto bus222. Multiplier216multiplies Y(0) with X(2) to produce the inverted or noninverted product signal at its output port216o. Adder220adds the output from of multiplexer232with the product from multiplier output port216o. This procedure continues until the Nthclock cycle (the last or N−1thclock cycle of the first set ofFIG. 3a).

At the Nthclock cycle (the last or N−1thclock cycle of the first set ofFIG. 3a), the sum then at the output port220oof adder220is stored in shift register2240, and the contents of the shift registers of delay224are not shifted to the left; the output from register224N−1is the last zero value. Multiplexer230is set to output X(n) the last bit of the X word, and multiplexer232is set to output the zero-value word available on bus223. Multiplier216multiplies Y(0) with X(n) to produce a product. Adder220adds the product from output port2160of multiplier216with output of multiplexer232. This completes the correlation of the X word with the current Y word, Y(0). It should be noted that in the arrangement ofFIG. 2, corresponding to the first correlator of a cascade of correlators, the value coupled by multiplexer232onto bus222is always zero. In other correlators of a cascade, the value coupled onto bus222may in general be nonzero.

At the next or N+1thclock cycle, which is the 0thclock cycle of the second set of CLK pulses ofFIG. 3a(and which corresponds to the second CLK/N pulse {pulse1} ofFIG. 3b), the next value or multibit word Y(1) of input signal Y is stored in register212, and becomes available on bus214. This second Y value or word will be correlated bit-by-bit with the same X word previously applied to the input of multiplexer230. At the N+1thclock cycle (the 1thCLK/N pulse), multiplexer230is set to output X(0). The sum signal then at the output port220oof adder220is stored in register240. Multiplier216multiplies Y(1) with X(0) to produce an inverted or noninverted product, depending upon the value of X(0). It will be noted that multiplexer232is again set to output the zero value from bus221; the value of zero is applied to bus222at the beginning of each set of N clock cycles (or at each CLK/N clock cycle) when the structure210ofFIG. 2processes the N-least-significant-digits 0 through N of the large X and Y words being processed. However, when the structure210ofFIG. 2is used to process digits of significance greater than the least, multiplexer232is handled differently, as described below. Since arrangement210ofFIG. 2represents the lowest-significant-digit processing, adder220receives zero from multiplexer232and adds zero with output of multiplier216o.

During CLK Cycle n+2 (CLK pulse N+1), the signal at output220oof adder220is transferred into shift register2240. Multiplexer230set to output X(1). Multiplexer232is set to couple onto bus222the output from register224N−1. Multiplier216multiplies Y(1) with X(1). Adder220adds the output from the output port of multiplexer232with output260oof multiplier216.

The operation continues in like fashion. At CLK pulse or cycle2n(corresponding once again to the 0thcycle of the modulo-N clock), the signal at the output port220oof adder220is transferred into shift register2240. Multiplexer230set to output X(N). Multiplexer232set to couple to bus222the output of register224N−1. Multiplier216multiplies Y(1) with X(n). Adder220adds the output of multiplexer232with output of multiplier216o.

During CLK cycle2N+1(corresponding to the third CLK/N pulse, designated2inFIG. 3b) the output from adder output port220ois stored in register240. The next value of Y is stored in register212, and multiplexer230is set to output X(0). Multiplexer232is set to couple onto bus222the output from register224N−1. Multiplier216multiplies Y(2) with X(0), and adder220adds zero with the output of multiplier216o. This process continues until all Y values have been processed against all the bits of X.

FIG. 4is a simplified block diagram illustrating a structure410for the cascading of a plurality of N-bit correlators such as210ofFIG. 2in order to correlate X and Y values having large numbers of bits. In the cascade ofFIG. 4, each of the N-bit correlators of the cascade (except the first) receives partial correlation results from the previous N-bit correlator of the cascade, and receives a different set of X bits from the entire X word. Each of the N-bit correlators ofFIG. 4also receives the entire Y-word. InFIG. 4, the left-most N-bit correlator is designated210, to indicate its relationship to the structure ofFIG. 2. More particularly, in structure410, the multibit Y word is applied to port1P of N-bit correlator210, as inFIG. 2. The multibit Y word is also applied to the corresponding input ports1P′,1P″, . . . ,1Psof N-bit correlators210′,210″, . . . ,210s. The correlated output is taken from output210oof N-bit correlator210on signal path250for application to the input port221′ of N-bit correlator210′, the correlated output is taken from output210o′ of N-bit correlator210′ on signal path250′ for application to the input port221″ of N-bit correlator210″, and the correlated output is taken from the penultimate N-bit correlator (not illustrated) for application to the input port221sof N-bit correlator210s. The X word bits which are applied to second N-bit correlator210′ are X(N), X(N+1), . . . , X(2N). The results of correlation by second N-bit correlator210′ are generated at its output port210o′, and are coupled over a path250′ to the input port1P″ of a third N-bit correlator210″. Third N-bit correlator210″ receives X bits X(2N+1), X(2N+2), . . . , X(3N) and correlates them with the partial results applied to its input port1P″. This process continues until the partial results are applied to the input port221sof last N-bit correlator210s. Last N-bit correlator210sreceives X bits X((S−1)N), . . . , X(SN), and correlates with the X words the partial correlation applied to its input port221s, to produce the correlation Rxyat a cascade output port410o.

While the multiplier216ofFIG. 2has been described as multiplying the Y word by +1 if the current bit of the X word is a logic 1 and by −1 if the current bit of the X word is a logic 0, it can instead multiply the Y word by −1 if the current bit of the X word is logic 1 and by +1 if the current bit of the X word is logic 0.

In general, an apparatus for correlating multibit first and second words according to an aspect of the invention includes a multiplexer for selecting one bit at a time of the second word, and applying the bit to a multiplier which receives the first word, for generating a product by inverting or noninverting the first word. The product is applied to an adder and is added to a delayed parallel signal to produce a sum signal. The sum signal is delayed in an amount related to the number of bits in the first word to produce the delayed parallel signal. A plurality of such apparatuses are cascaded, with the bits of the second word applied in subsets to the apparatuses, and the partial correlations applied as input words to the next apparatus in the cascade.

An apparatus (210) according to an aspect of the invention is for correlating multibit first (Y) and second (X) signals. The apparatus (210) includes a multiplexer (230) with a multibit input port (230i) coupled to receive the second signal (X), and also includes a single-bit output port (2300), for selectively coupling to its output port (230o) one bit at a time of the multibit second signal (X). A multiplier (216) includes an output port, (216o), a first multibit input port (216i1) and second single-bit input port (216i2) coupled to the output port (230o) of the multiplexer (230). The multiplier (216) is coupled for receiving the first signals (Y) in parallel form (at its first input port216i1), for controllably coupling to its output port (216o) a multibit product signal in response to the one bit of the second signal (X) applied to its second input port (216i2). The multiplier (216), in one embodiment, multiplies the words of the first signal (Y) by +1 if the one bit of the second digital signal (X) applied to its second input port (230i2) has a logical value of 1 and by −1 if the one bit of the second digital signal (X) applied to its second input port (230i2) has a logical value of 0. The multiplier (216), in another embodiment, multiplies the words of the first signal (Y) by −1 if the one bit of the second digital signal (X) applied to its second input port (230i2) has a logical value of 1 and by +1 if the one bit of the second digital signal (X) applied to its second input port (230i2) has a logical value of 0. The apparatus (210) further includes summing means (220) including an input port (220i1) coupled to the output port (2160) of the multiplier (216), for summing the multibit product signals received from the multiplier (216) with delayed parallel signals (applied over path222), to thereby produce (at port220o) summed parallel signals representing the correlated output. A delay means or arrangement (224,232) is coupled to receive the summed parallel signals, for delaying the summed parallel signals for a number of clock cycles N equal to the number of bits (N) in the digital first signals (X), for thereby producing the delayed parallel signals.

A particular embodiment of the arrangement (210), includes means for coupling the words of the second signal (Y) to the first input port (216i1) of the multiplier (216). The means for coupling may comprise a register (212) clocked at a rate (Clk/N) lower than that of the multiplexer (230).

A particular embodiment of the arrangement (210) further comprises a clocked register (240) having an input port (240i) coupled to receive the summed parallel signals representing the correlated output.

In another embodiment, the means for coupling the words of the first signal (Y) to the first input port (216i1) of the multiplier (216) comprises a first register (212) clocked at a rate lower than that of the first multiplexer (230). This embodiment further comprises a clocked second register (240) having an input port (240i) coupled to receive the summed parallel signals representing the correlated output, with the second register (240) being clocked at the same, rate as the first register (212).

Initialization or cascading of the correlation apparatus (210) may be provided by an embodiment which further comprises second multiplexing means (232) coupled to the summing means (220), for applying an initialization value to the summing means (220).

A method for correlating first and second multibit signals includes the step of applying the first signals (Y) to a first input port (216i1) of a multiplier (216), where the multiplier (216) includes a single-bit second input port (216i2) and an output port (216o). The application of the first signal is for a period of at least N clock cycles. The bits of the multibit second signal (X) are gated (230) to the single-bit second input port (216i2) of the multiplier (216), for sequentially multiplying the first input signal (Y) by the individual bits of the second input signal (X), for thereby producing multiplied multibit signals (at port216o). The multiplied multibit signals are applied to a first input port (220i1) of an adder (220), which adder (220) includes a second input port (220i2) and an output port (220o) at which added signals are generated. The added signals are delayed (214) by a number of clock cycles at least equal to the number of bits (N) in the first multibit signal (X), to thereby produce delayed signals. The delayed signals are applied to the second input port (220i2) of the adder (220), whereby the added signals (at port2200) include the result (Rxy) of the correlation. The results of the correlation are extracted (240) from the added signals.

An apparatus (410) according to an aspect of the invention is for correlating M-bit first (Y) and second (X) signals. The apparatus (410) comprises a plurality of N-bit correlators (210,210′,210″, . . . ,210s), where N is less than M. Each of the N-bit correlators (210,210′,210″, . . . ,210s) of the plurality comprises(a) an N-bit multiplexer including an N-bit input port (230i) coupled to receive a subset of bits of the M-bit second (X) signal, and also including a single-bit output port (230o), for selectively coupling to its output port (230o) one bit at a time of the subset of bits (of X);(b) a multiplier (216) including an output port (216o), a first multibit input port (216i1) and second single-bit input port (216i2), the single-bit input port (216i2) of the multiplier (216) being coupled to the output port (230o) of the multiplexer (230) for receiving the one bit at a time, the multiplier (216) being coupled for receiving the first signals (Y) in parallel form at its first input port (216i1), for controllably coupling to its output port (216o) a multibit product signal in response to that one bit of the second signal (X) applied to its second input port (216i2), and for one of (a) multiplying the words of the first signal (Y) by +1 if the one bit of the second digital signal (X) applied to its second input port (216i2) has a logical value of 1 and by −1 if the one bit of the second digital signal (X) applied to its second input port (216i2) has a logical value of 0, and (b) multiplying the words of the first signal (Y) by −1 if the one bit of the second digital signal (X) applied to its second input port (216i2) has a logical value of 1 and by +1 if the one bit of the second digital signal (X) applied to its second input port (216i2) has a logical value of 0;(c) summing means (220) including an input port (220i1) coupled to the output port (216o) of the multiplier (216), for summing the multiplied parallel signals received from the multiplier (216) with delayed parallel signals (on bus222), to thereby produce summed parallel signals (at port220o) representing the correlated output; and(d) delay means (224) coupled to receive the summed parallel signals, for delaying the summed parallel signals for a number of clock cycles at least equal to the number of bits in the digital first signals (Y), for thereby producing the delayed parallel signals (on bus222).
The apparatus (410) according to this aspect of the invention includes means (240;250,250′,250″, . . . ) for selectively applying the summed parallel signals representing the correlated output from one (210) of the N-bit correlators to the next one (210′) of the N-bit correlators (210) in the cascade (410).

A method according to another aspect of the invention is for correlating first (Y) and second (X) multibit signals. The method comprises the step of applying the multibit first (Y) signals to a first input port216i2of a multiplier (216) which includes a single-bit second input port (216i2) and an output port (216o). The method further includes the step of, while the multibit first signals (Y) are applied to the first input port (216i1) of the multiplier (216), sequentially gating (by230) the bits of the multibit second signal (X) to the single-bit second input port (216i2) of the multiplier (216), for sequentially multiplying the first input signal (Y) by the individual bits of the second (X) input signal for thereby producing (on path218) multiplied multibit signals. The multiplied multibit signals are applied to a first input port (220i1) of an adder (220), which adder (220) includes a second input port (220i2) for receiving delayed signals (from path222), and an output port (220o) at which added signals are generated representing the sum of the multiplied multibit signals with the delayed signals. The added signals are delayed (224) by a number of clock cycles at least equal to the number of bits in the first multibit signal (Y), to thereby produce the delayed signals. The delayed signals are applied to the second input port (220i2) of the adder, whereby the added signals include the result of the correlation. A particular mode of this method comprises the step of extracting the result (240) of the correlation from the added signals.