Correlation

Collaboration diagram for Correlation:

Functions
void	tpt_correlate_f32 (f32_t *aOutData, const f32_t *aInDataA, uint32_t aLenA, const f32_t *aInDataB, uint32_t aLenB)
	Correlation of floating-point sequences.
void	tpt_correlate_f64 (f64_t *aOutData, const f64_t *aInDataA, uint32_t aLenA, const f64_t *aInDataB, uint32_t aLenB)
	Correlation of floating-point sequences.
tpt_status	tpt_correlate_fast_f32 (f32_t *aOutData, const f32_t *aInDataA, uint32_t aLenA, const f32_t *aInDataB, uint32_t aLenB)
	Correlation of floating-point sequences (fast version).
void	tpt_correlate_fast_opt_q15 (q15_t *pDst, const q15_t *pSrcA, uint32_t srcALen, const q15_t *pSrcB, uint32_t srcBLen, q15_t *pScratch)
	Correlation of Q15 sequences (fast version).
void	tpt_correlate_fast_q15 (q15_t *pDst, const q15_t *pSrcA, uint32_t srcALen, const q15_t *pSrcB, uint32_t srcBLen)
	Correlation of Q15 sequences (fast version).
void	tpt_correlate_fast_q31 (q31_t *pDst, const q31_t *pSrcA, uint32_t srcALen, const q31_t *pSrcB, uint32_t srcBLen)
	Correlation of Q31 sequences (fast version).
void	tpt_correlate_q15 (q15_t *aOutData, const q15_t *aInDataA, uint32_t aLenA, const q15_t *aInDataB, uint32_t aLenB)
	Correlation of Q15 sequences.
void	tpt_correlate_q31 (q31_t *aOutData, const q31_t *aInDataA, uint32_t aLenA, const q31_t *aInDataB, uint32_t aLenB)
	Correlation of Q31 sequences.
void	tpt_correlate_q7 (q7_t *aOutData, const q7_t *aInDataA, uint32_t aLenA, const q7_t *aInDataB, uint32_t aLenB)
	Correlation of Q7 sequences.

Detailed Description

Correlation is a mathematical operation that is similar to convolution. As with convolution, correlation uses two signals to produce a third signal. The underlying algorithms in correlation and convolution are identical except that one of the inputs is flipped in convolution. Correlation is commonly used to measure the similarity between two signals. It has applications in pattern recognition, cryptanalysis, and searching. The DSP library provides correlation functions for Q15, Q31 and floating-point data types. Fast versions of the floating-point functions are also provided.

Algorithm

Let a[n] and b[n] be sequences of length aLenA and aLenB samples respectively. The convolution of the two signals is denoted by

    c[n] = a[n] * b[n]
  

In correlation, one of the signals is flipped in time

    c[n] = a[n] * b[-n]
  

and this is mathematically defined as

The aInDataA points to the first input vector of length aLenA and aInDataB points to the second input vector of length aLenB. The result c[n] is of length 2 * max(aLenA, aLenB) - 1 and is defined over the interval n = 0, 1, 2, ..., (2 * max(aLenA, aLenB) - 2). The output result is written to aOutData and the calling function must allocate 2 * max(aLenA, aLenB) - 1 words for the result.

Note

The aOutData should be initialized to all zeros before being used.

Fixed-Point Behavior

Correlation requires summing up a large number of intermediate products. As such, the Q15, and Q31 functions run a risk of overflow and saturation. Refer to the function specific documentation below for further details of the particular algorithm used.

Fast Versions

Fast versions are supported for floating-point. Time complexity for Fast versions are less compared to floating-point of conv and the design consumes more memory.

Algorithm

Let a[n] and b[n] be sequences of length aLenA and aLenB samples respectively. The convolution of the two signals is denoted by

    c[n] = a[n] * b[n]
  

In correlation, one of the signals is flipped in time

    c[n] = a[n] * b[-n]
  

and this is mathematically defined as

The aInDataA points to the first input vector of length aLenA and aInDataB points to the second input vector of length aLenB. The result c[n] is of length 2 * max(aLenA, aLenB) - 1 and is defined over the interval n = 0, 1, 2, ..., (2 * max(aLenA, aLenB) - 2). The output result is written to aOutData and the calling function must allocate 2 * max(aLenA, aLenB) - 1 words for the result.

Note

The aOutData should be initialized to all zeros before being used.

Fixed-Point Behavior

Correlation requires summing up a large number of intermediate products. As such, the Q15, and Q31 functions run a risk of overflow and saturation. Refer to the function specific documentation below for further details of the particular algorithm used.

Fast Versions

Fast versions are supported for floating-point. Time complexity for Fast versions are less compared to floating-point of conv and the design consumes more memory.

Function Documentation

tpt_correlate_f32()

void tpt_correlate_f32	(	f32_t *	aOutData,
		const f32_t *	aInDataA,
		uint32_t	aLenA,
		const f32_t *	aInDataB,
		uint32_t	aLenB )

Correlation of floating-point sequences.

Parameters

[out]	aOutData	points to the location where the output result is written. Length 2 * max(aLenA, aLenB) - 1.
[in]	aInDataA	points to the first input sequence
[in]	aLenA	length of the first input sequence
[in]	aInDataB	points to the second input sequence
[in]	aLenB	length of the second input sequence

Returns

none

Remarks

Refer to tpt_correlate_fast_f32() for a faster but consumes more memory of this function.

tpt_correlate_f64()

void tpt_correlate_f64	(	f64_t *	aOutData,
		const f64_t *	aInDataA,
		uint32_t	aLenA,
		const f64_t *	aInDataB,
		uint32_t	aLenB )

Correlation of floating-point sequences.

Parameters

[out]	aOutData	points to the location where the output result is written. Length 2 * max(aLenA, aLenB) - 1.
[in]	aInDataA	points to the first input sequence
[in]	aLenA	length of the first input sequence
[in]	aInDataB	points to the second input sequence
[in]	aLenB	length of the second input sequence

Returns

none

Remarks

Refer to tpt_correlate_fast_f64() for a faster but consumes more memory of this function.

tpt_correlate_fast_f32()

tpt_status tpt_correlate_fast_f32	(	f32_t *	aOutData,
		const f32_t *	aInDataA,
		uint32_t	aLenA,
		const f32_t *	aInDataB,
		uint32_t	aLenB )

Correlation of floating-point sequences (fast version).

Parameters

[out]	aOutData	points to the location where the output result is written. Length 2 * max(aLenA, aLenB) - 1.
[in]	aInDataA	points to the first input sequence.
[in]	aLenA	length of the first input sequence
[in]	aInDataB	points to the second input sequence.
[in]	aLenB	length of the second input sequence

Returns

execution status

• TPT_MATH_SUCCESS : Operation is successful.
• TPT_MATH_ARGUMENT_ERROR : length is not supported.

tpt_correlate_fast_opt_q15()

void tpt_correlate_fast_opt_q15	(	q15_t *	pDst,
		const q15_t *	pSrcA,
		uint32_t	srcALen,
		const q15_t *	pSrcB,
		uint32_t	srcBLen,
		q15_t *	pScratch )

Correlation of Q15 sequences (fast version).

Parameters

[out]	pDst	points to the location where the output result is written. Length 2 * max(srcALen, srcBLen) - 1.
[in]	pSrcA	points to the first input sequence
[in]	srcALen	length of the first input sequence
[in]	pSrcB	points to the second input sequence
[in]	srcBLen	length of the second input sequence.
[in]	pScratch	points to scratch buffer of size max(srcALen, srcBLen) + 2*min(srcALen, srcBLen) - 2.

Scaling and Overflow Behavior

This fast version uses a 32-bit accumulator with 2.30 format. The accumulator maintains full precision of the intermediate multiplication results but provides only a single guard bit. There is no saturation on intermediate additions. Thus, if the accumulator overflows it wraps around and distorts the result. The input signals should be scaled down to avoid intermediate overflows. Scale down one of the inputs by 1/min(srcALen, srcBLen) to avoid overflow since a maximum of min(srcALen, srcBLen) number of additions is carried internally. The 2.30 accumulator is right shifted by 15 bits and then saturated to 1.15 format to yield the final result.

Remarks

Refer to tpt_correlate_q15() for a slower implementation of this function which uses a 64-bit accumulator to avoid wrap around distortion.

Returns

none

tpt_correlate_fast_q15()

void tpt_correlate_fast_q15	(	q15_t *	pDst,
		const q15_t *	pSrcA,
		uint32_t	srcALen,
		const q15_t *	pSrcB,
		uint32_t	srcBLen )

Correlation of Q15 sequences (fast version).

Parameters

[out]	pDst	points to the location where the output result is written. Length 2 * max(srcALen, srcBLen) - 1.
[in]	pSrcA	points to the first input sequence
[in]	srcALen	length of the first input sequence
[in]	pSrcB	points to the second input sequence
[in]	srcBLen	length of the second input sequence

Scaling and Overflow Behavior

This fast version uses a 32-bit accumulator with 2.30 format. The accumulator maintains full precision of the intermediate multiplication results but provides only a single guard bit. There is no saturation on intermediate additions. Thus, if the accumulator overflows it wraps around and distorts the result. The input signals should be scaled down to avoid intermediate overflows. Scale down one of the inputs by 1/min(srcALen, srcBLen) to avoid overflow since a maximum of min(srcALen, srcBLen) number of additions is carried internally. The 2.30 accumulator is right shifted by 15 bits and then saturated to 1.15 format to yield the final result.

Remarks

Refer to tpt_correlate_q15() for a slower implementation of this function which uses a 64-bit accumulator to avoid wrap around distortion.

Returns

none

tpt_correlate_fast_q31()

void tpt_correlate_fast_q31	(	q31_t *	pDst,
		const q31_t *	pSrcA,
		uint32_t	srcALen,
		const q31_t *	pSrcB,
		uint32_t	srcBLen )

Correlation of Q31 sequences (fast version).

Parameters

[out]	pDst	points to the location where the output result is written. Length 2 * max(srcALen, srcBLen) - 1.
[in]	pSrcA	points to the first input sequence
[in]	srcALen	length of the first input sequence
[in]	pSrcB	points to the second input sequence
[in]	srcBLen	length of the second input sequence

Scaling and Overflow Behavior

This function is optimized for speed at the expense of fixed-point precision and overflow protection. The result of each 1.31 x 1.31 multiplication is truncated to 2.30 format. These intermediate results are accumulated in a 32-bit register in 2.30 format. Finally, the accumulator is saturated and converted to a 1.31 result.

The fast version has the same overflow behavior as the standard version but provides less precision since it discards the low 32 bits of each multiplication result. In order to avoid overflows completely the input signals must be scaled down. The input signals should be scaled down to avoid intermediate overflows. Scale down one of the inputs by 1/min(srcALen, srcBLen) to avoid overflows since a maximum of min(srcALen, srcBLen) number of additions is carried internally.

Remarks

Refer to tpt_correlate_q31() for a slower implementation of this function which uses 64-bit accumulation to provide higher precision.

Returns

none

tpt_correlate_q15()

void tpt_correlate_q15	(	q15_t *	aOutData,
		const q15_t *	aInDataA,
		uint32_t	aLenA,
		const q15_t *	aInDataB,
		uint32_t	aLenB )

Correlation of Q15 sequences.

Parameters

[out]	aOutData	points to the location where the output result is written. Length 2 * max(aLenA, aLenB) - 1.
[in]	aInDataA	points to the first input sequence
[in]	aLenA	length of the first input sequence
[in]	aInDataB	points to the second input sequence
[in]	aLenB	length of the second input sequence

Returns

none

Scaling and Overflow Behavior

The function is implemented using a 64-bit internal accumulator. Both inputs are in 1.15 format and multiplications yield a 2.30 result. The 2.30 intermediate results are accumulated in a 64-bit accumulator in 34.30 format. This approach provides 33 guard bits and there is no risk of overflow. The 34.30 result is then truncated to 34.15 format by discarding the low 15 bits and then saturated to 1.15 format.

tpt_correlate_q31()

void tpt_correlate_q31	(	q31_t *	aOutData,
		const q31_t *	aInDataA,
		uint32_t	aLenA,
		const q31_t *	aInDataB,
		uint32_t	aLenB )

Correlation of Q31 sequences.

Parameters

[out]	aOutData	points to the location where the output result is written. Length 2 * max(aLenA, aLenB) - 1.
[in]	aInDataA	points to the first input sequence.
[in]	aLenA	length of the first input sequence
[in]	aInDataB	points to the second input sequence.
[in]	aLenB	length of the second input sequence

Returns

none

Scaling and Overflow Behavior

The function is implemented using an internal 64-bit accumulator. The accumulator has a 2.62 format and maintains full precision of the intermediate multiplication results but provides only a single guard bit. There is no saturation on intermediate additions. Thus, if the accumulator overflows it wraps around and distorts the result. The input signals should be scaled down to avoid intermediate overflows. Scale down one of the inputs by 1 / min(aLenA, aLenB) to avoid overflows since a maximum of min(aLenA, aLenB) number of additions is carried internally. The 2.62 accumulator is right shifted by 31 bits and saturated to 1.31 format to yield the final result.

tpt_correlate_q7()

void tpt_correlate_q7	(	q7_t *	aOutData,
		const q7_t *	aInDataA,
		uint32_t	aLenA,
		const q7_t *	aInDataB,
		uint32_t	aLenB )

Correlation of Q7 sequences.

Correlation of Q15 sequences.

Parameters

[out]	aOutData	points to the location where the output result is written. Length 2 * max(aLenA, aLenB) - 1.
[in]	aInDataA	points to the first input sequence
[in]	aLenA	length of the first input sequence
[in]	aInDataB	points to the second input sequence
[in]	aLenB	length of the second input sequence

Returns

none

Scaling and Overflow Behavior

The function is implemented using a 32-bit internal accumulator. Both inputs are in 1.7 format and multiplications yield a 2.14 result. The 2.14 intermediate results are accumulated in a 64-bit accumulator in 18.14 format. This approach provides 17 guard bits and there is no risk of overflow. The 18.14 result is then truncated to 18.7 format by discarding the low 7 bits and then saturated to 1.7 format.